P7320 "PMOI-4" Poor Group Leader

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**?

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**.

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!`.

[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