Problem Description

lnlhm is given a simple, undirected, connected graph with $n$ vertices and $m$ edges. Soon, he gets targeted by ducati and b6e0.

ducati wants to find exactly $\left \lceil \frac n 6 \right \rceil$ distinct paths such that every vertex is visited by at least one path.

b6e0 wants to find a vertex set of size exactly $\lfloor \frac n 3 \rfloor$ such that there is no edge between any pair of vertices in the set.

lnlhm knows that if he does not satisfy someone’s requirement, he will be beaten. So he asks you for help: is there a way to choose edges or vertices so that at most one person beats him?

Input Format

The first line contains two positive integers $n,m$, representing the number of vertices and the number of edges.

The next $m$ lines each contain two vertices $u,v$, describing an undirected edge.

Output Format

If you want to satisfy ducati’s requirement, output $1$ on the first line, and then output $\left \lceil \frac {n} 6 \right \rceil$ paths in the next lines, one path per line. You must ensure that these paths are pairwise distinct (for example, you cannot output both $5 \to 3 \to 1$ and $1 \to 3 \to 5$). The format of one path is as follows:

• First output a positive integer $k(1\le k\le n)$, the number of vertices on the path.

• Then output $k$ positive integers, the vertices on the path, separated by spaces. You need to ensure that every pair of adjacent vertices has an edge between them, no vertex is visited at least twice by any single path, and every vertex is visited by at least one path.

If you want to satisfy b6e0’s requirement, output $2$ on the first line, and then output $\lfloor \frac n 3 \rfloor$ vertices on the second line to represent the chosen independent set, separated by spaces.

In particular, if neither requirement can be satisfied, output one line Poor lnlhm!.

6 7
1 2
1 3
2 3
2 5
4 5
5 6
4 6

2
1 4

6 6
1 2
2 3
3 4
4 5
5 6
1 6

1
6 1 2 3 4 5 6

Hint

[Sample Explanation]

For the first sample, we only need to choose the vertex set $\{1,4\}$ for b6e0. Note that $\{1,5\}\{1,6\}\{2,4\}\{2,6\}\{3,4\}\{3,5\}\{3,6\}$ are also valid.

For the second sample, we only need to choose the path $1 \to 2 \to 3 \to 4 \to 5 \to 6$ for ducati.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (20pts): $n,m\le10$.
• Subtask 2 (20pts): the graph is guaranteed to be a tree.
• Subtask 3 (60pts): no special constraints.

For $100\%$ of the testdata, $3\le n\le10^3$, $3\le m\le\dfrac{n(n-1)}2$, and the given graph is guaranteed to be a simple, undirected, connected graph.

Friendly reminder: the input size is large, so please use a fast input method.

Translated by ChatGPT 5