Odd Cycle or 3-Coloring

题目描述

You are given a connected, simple, undirected graph with $n$ vertices and $m$ edges.

We call a simple cycle safely removable if deleting all of its edges keeps the graph connected.

You should complete exactly one of the two tasks below (you choose which one), and you do not need to do both. It can be proved that at least one of the two tasks is always achievable.

1. 3-color the graph: give each vertex a color in $\{1,2,3\}$ so that the two endpoints of every edge get different colors.

2. Find a safely removable odd cycle: output a simple cycle of odd length that is safely removable.

输入格式

The first line contains $n$ and $m$. Each of the next $m$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$), meaning there is an edge between vertices $x$ and $y$. The graph is connected and has no self-loops or repeated edges.

$1 \le n \le 10^{5}$, $1 \le m \le 2 \cdot 10^{5}$.

输出格式

For task 1, print $\mathbf{1}$, then a line of $n$ integers $c_1, \ldots, c_n$ ($1 \le c_i \le 3$).

For task 2, print $\mathbf{2}$, then a line with the odd cycle length $L$ followed by the $L$ cycle vertices $v_1, \ldots, v_L$ in order.

Any valid answer is accepted by a special judge.

样例输入 #1

3 3
1 2
3 2
1 3

样例输出 #1

1
1 2 3

样例输入 #2

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

样例输出 #2

2
3 3 4 2

样例输入 #3

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

样例输出 #3

1
1 1 1 2 1 2