题目描述

Salme 非常喜欢数学。她尤其喜欢具有某些特殊性质的图。

更准确地说，Salme 喜欢满足以下条件之一的图：

1. 图中存在两个长度为奇数的环，并且这两个环没有公共边；
2. 图的所有顶点可以使用至多四种颜色染色，使得任意一条边连接的两个顶点颜色都不同。

Salme 的朋友 Linda 发现，实际上 Salme 喜欢所有图。请帮助 Linda 证明这一点。

为此，你需要编写程序：对于任意给定图，找出两个没有公共边的奇环，或者给出一个至多四种颜色的合法顶点染色。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M$（$1 \le N \le 5 \cdot 10^5$，$0 \le M \le 5 \cdot 10^5$），分别表示图的顶点数和边数。顶点编号为 $1,2,\ldots,N$。

接下来 $M$ 行，每行包含两个用空格分隔的整数 $U_i$ 和 $V_i$（$1 \le U_i,V_i \le N$），表示顶点 $U_i$ 与 $V_i$ 之间有一条边。

图是无向图。可以保证图是连通图，并且任意两个顶点之间至多有一条边。

输出格式

第一行输出 1 或 2，表示你选择证明图满足哪一种条件：

• 输出 1：表示图中存在符合要求的两个奇环；
• 输出 2：表示图中存在符合要求的至多四种颜色染色。

如果第一行输出 1，则：

• 第二行输出两个用空格分隔的整数 $X$ 和 $Y$，分别表示第一个环和第二个环包含的顶点数；
• 第三行输出 $X$ 个用空格分隔的整数，表示第一个环中的顶点编号，按它们在环上出现的顺序给出；
• 第四行输出 $Y$ 个用空格分隔的整数，表示第二个环中的顶点编号，按它们在环上出现的顺序给出。

这两个环都必须是奇环，并且不能有公共边。它们可以有公共顶点。

如果第一行输出 2，则第二行输出 $N$ 个用空格分隔的整数 $C_1,C_2,\ldots,C_N$，其中 $C_i$（$1 \le C_i \le 4$）表示顶点 $i$ 的颜色编号。

如果存在多个合法答案，输出任意一个即可。

样例 1

输入

9 11
1 2
1 3
2 3
2 4
3 4
4 5
4 6
4 7
6 8
8 9
7 9

输出

1
3 5
2 3 4
4 6 8 9 7

原题此处有一张图：程序找到的两个奇环用不同颜色标出。在这个样例中，第二个环不能选择 1 2 3，因为这样两个环会共用边 $2-3$。

样例 2

输入

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

输出

2
1 2 3 1 4 1 2

原题此处有一张图：展示了程序找到的染色。不同颜色的顶点除了填充颜色不同外，还用不同的边框样式标出。

评分方式

本题测试点按组计分。只有通过某个分组中的所有测试点，才能获得该组分数。分组如下：

1.（0 分）题面中的样例。
2.（40 分）$N \le 10^3$，$M \le 10^4$。
3.（40 分）无额外限制。