题目描述

lnlhm 被塞给了一张 $n$ 个点 $m$ 条边的简单无向连通图。很快，他就被 ducati 和 b6e0 盯上了。

ducati 希望能够从中找到恰好 $\left \lceil \frac n 6 \right \rceil$ 条不同的路径，使得所有的点都被至少一条路径经过。

b6e0 希望找到一个大小恰好为 $\lfloor \frac n 3 \rfloor$ 的节点集合，使得它们之间两两没有边。

lnlhm 知道，如果他没有满足某个人的要求，那么他就会被揍。因此，他向你求助：是否存在一种选择边或点的方案，使得最多被一个人揍？

输入格式

第一行两个正整数 $n,m$，表示点数以及边数。

下面 $m$ 行，每行两个点 $u,v$，描述一条无向边。

输出格式

若想要满足 ducati 的需求，在第一行输出 $1$，并在下面的 $\left \lceil \frac {n} 6 \right \rceil$ 行中，每行输出一条路径，你需要保证这些路径两两不同（例如，不能同时输出 $5 \to 3 \to 1$ 和 $1 \to 3 \to 5$）。输出一条路径的格式如下：

• 先输出一个正整数 $k(1\le k\le n)$，表示路径经过的节点数。

• 接下来 $k$ 个正整数，表示路径上的点，点之间用空格隔开。你需要保证，每相邻两个点之间有连边，不存在一个点被某条路径经过不少于两次，且每个点均被至少一条路径经过。

若想要满足 b6e0 的需求，在第一行输出 $2$，并在第二行中输出 $\lfloor \frac n 3 \rfloor$ 个点表示选出的独立集，之间用空格隔开。

特别的，若两个人的要求一个也无法满足，那么输出一行 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

提示

【样例解释】

对于第一组样例，我们只需要为 b6e0 选出节点集合 $\{1,4\}$ 即可。注意，$\{1,5\}\{1,6\}\{2,4\}\{2,6\}\{3,4\}\{3,5\}\{3,6\}$ 同样合法。

对于第二组样例，我们只需要为 ducati 选出路径 $1 \to 2 \to 3 \to 4 \to 5 \to 6$ 即可。

【数据范围】

本题采用捆绑测试。

• Subtask 1（20pts）：$n,m\le10$。
• Subtask 2（20pts）：保证图为一棵树。
• Subtask 3（60pts）：无特殊限制。

对于 $100\%$ 的数据满足，$3\le n\le10^3$，$3\le m\le\dfrac{n(n-1)}2$，保证给定的图为简单无向连通图。

温馨提示: 输入量较大，请使用较快的读入方式。