Paths or Independent Set?

You are given a simple, undirected, connected graph with n vertices and m edges. Two adversaries have made two different demands:

• ducati requires you to select exactly \(\lceil\frac{n}{6}\rceil\) different simple paths such that every vertex of the graph lies in at least one of these paths.
• b6e0 requires you to select a set of vertices of exactly size \(\lfloor\frac{n}{3}\rfloor\) which is independent (i.e. no two vertices in the set share an edge).

lnlhm, who has been given the graph, is in trouble – if he fails to satisfy someone’s requirement he’ll get beaten up. He wonders if it is possible to choose either a set of paths or a set of vertices so that at most one of the two parties gets what they asked (i.e. you are allowed to fail one, but not both).

Input format

The first line contains two integers n and m \((2 \le n, m \le 2 \cdot 10^5)\), denoting the number of vertices and edges respectively. The next m lines each contain two integers u and v \((1 \le u,v \le n, u \neq v)\) representing an edge between vertices u and v. It is guaranteed that the graph is simple and connected.

Output format

If a valid selection exists (and it is known that one always exists by theory), you should output a solution in one of the following two formats:

1. Independent Set solution:
   • On the first line, print 1.
   • On the second line, print exactly \(\lfloor\frac{n}{3}\rfloor\) distinct integers, the vertices that form an independent set.
2. Path solution:
   • On the first line, print 2.
   • Then print exactly \(\lceil\frac{n}{6}\rceil\) lines. For each path, first output an integer k denoting the number of vertices in the path, followed by k vertices representing the simple path (consecutive vertices must be adjacent in the graph).

You are allowed to output any one of the two types of valid solutions. Note that the vertices in an independent set are guaranteed not to have any edge between them, and the paths in the path solution must be simple (no repeated vertices) though paths are allowed to share vertices across different paths, as long as every vertex is covered by at least one path.

Explanation: In this problem, you are essentially asked to decide whether there exists a method (either by selecting vertices or by selecting paths) such that lnlhm avoids getting beaten by satisfying at least one party’s requirement.

inputFormat

The input begins with two integers n and m on the first line. The following m lines each contain two integers u and v indicating an edge between vertices u and v.

outputFormat

Output a valid solution in one of two formats. If you choose the independent set format, first print 1 and then a line containing exactly \(\lfloor\frac{n}{3}\rfloor\) vertices that form an independent set. Otherwise, if you choose the path format, first print 2 and then exactly \(\lceil\frac{n}{6}\rceil\) lines, each describing a simple path in the graph. The paths chosen must cover all n vertices (each vertex appears in at least one path).

sample

3 2
1 2
2 3

1
1