Problem: Given a connected undirected graph with n vertices and an integer k, you have to either:

  * either find an independent set that has exactly ⌈k/2⌉ vertices.
  * or find a simple cycle of length at most k. 



An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice. 

I have a proof that for any input you can always solve at least one of these problems, but it's left as an exercise for the reader.

Input

The first line contains three integers n, m, and k (3 ≤ k ≤ n ≤ 10^5, n-1 ≤ m ≤ 2 ⋅ 10^5) — the number of vertices and edges in the graph, and the parameter k from the statement.

Each of the next m lines contains two integers u and v (1 ≤ u,v ≤ n) that mean there's an edge between vertices u and v. It's guaranteed that the graph is connected and doesn't contain any self-loops or multiple edges.

Output

If you choose to solve the first problem, then on the first line print 1, followed by a line containing ⌈k/2⌉ distinct integers not exceeding n, the vertices in the desired independent set.

If you, however, choose to solve the second problem, then on the first line print 2, followed by a line containing one integer, c, representing the length of the found cycle, followed by a line containing c distinct integers not exceeding n, the vertices in the desired cycle, in the order they appear in the cycle.

Examples

Input


4 4 3
1 2
2 3
3 4
4 1


Output


1
1 3 

Input


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


Output


2
3
2 3 4 

Input


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


Output


2
3
1 2 3 

Input


5 4 5
1 2
1 3
2 4
2 5


Output


1
1 4 5 

Note

In the first sample:

<image>

Notice that printing the independent set \{2,4\} is also OK, but printing the cycle 1-2-3-4 isn't, because its length must be at most 3.

In the second sample:

<image>

Notice that printing the independent set \{1,3\} or printing the cycle 2-1-4 is also OK.

In the third sample:

<image>

In the fourth sample:

<image>

Solution (in JAVA):

Solution:
// Utilities
import java.io.*;
import java.util.*;

public class Main {
	static int N, M, K;
	static ArrayList<Integer>[] adj;
	static boolean[] vis;
	static ArrayList<Integer> even, odd;
	static int parity, tmp, loop;
	static int evenCnt = 0, oddCnt = 0;
	static int[] d, nxt;
	static int cnt;
	
	public static void main(String[] args) throws IOException {
		N = in.iscan(); M = in.iscan(); K = in.iscan();
		adj = new ArrayList[N+1];
		for (int i = 0; i <= N; i++) adj[i] = new ArrayList();
		int u, v;
		for (int i = 0; i < M; i++) {
			u = in.iscan(); v = in.iscan();
			adj[u].add(v); adj[v].add(u);
		}
		vis = new boolean[N+1];
		d = new int[N+1]; nxt = new int[N+1];
		Arrays.fill(d, Integer.MAX_VALUE); d[1] = 0;
		dfs1(1, -1);
		// If it does not terminate after dfs1, it means graph is a tree (no cycle)
		out.println(1);
		evenCnt = 0; oddCnt = 0;
		for (int i = 1; i <= N; i++) {
			if (d[i] % 2 == 0) evenCnt++;
			else oddCnt++;
		}
		if (evenCnt >= (K+1)/2) {
			cnt = 0;
			for (int i = 1; i <= N; i++) {
				if (d[i] % 2 == 0) {
					out.print(i + " ");
					cnt++;
				}
				if (cnt == (K+1)/2) break;
			}
		}
		else {
			cnt = 0;
			for (int i = 1; i <= N; i++) {
				if (d[i] % 2 == 1) {
					out.print(i + " ");
					cnt++;
				}
				if (cnt == (K+1)/2) break;
			}
		}
		out.close();
	} 
	
	static void dfs1(int idx, int pr) {
		vis[idx] = true; loop = -1;
		for (int u : adj[idx]) {
			if (vis[u] && u != pr && d[idx] > d[u] && loop == -1) loop = u;
		}
		if (loop == -1) {
			for (int u : adj[idx]) {
				if (!vis[u]) {
					d[u] = d[idx] + 1;
					nxt[idx] = u;
					dfs1(u, idx);
				}
			}
		}
		else {
			if (d[idx] > d[loop] && d[idx] - d[loop] + 1 <= K) {
				out.println(2); 
				out.println(d[idx]-d[loop]+1);
				tmp = loop;
				while (tmp != idx) {
					out.print(tmp + " ");
					tmp = nxt[tmp];
				}
				out.println(tmp);
				out.close();
				System.exit(0);
			}
			else if (d[idx] > d[loop]) {
				tmp = loop; parity = 0; 
				even = new ArrayList<Integer>(); odd = new ArrayList<Integer>();
				while (tmp != idx) {
					if (parity == 0) even.add(tmp);
					else odd.add(tmp);
					parity ^= 1;
					tmp = nxt[tmp];
				}
				if (even.size() >= (K+1)/2) {
					out.println(1);
					cnt = 0;
					for (int xx : even) {
						out.print(xx + " ");
						cnt++;
						if (cnt == (K+1)/2) break;
					}
				}
				else if (odd.size() >= (K+1)/2){
					out.println(1);
					cnt = 0;
					for (int xx : odd) {
						out.print(xx + " ");
						cnt++;
						if (cnt == (K+1)/2) break;
					}
				}
				else {
					out.println("Error");
				}
				out.close();
				System.exit(0);
			}
		}
	}
	
	static INPUT in = new INPUT(System.in);
	static PrintWriter out = new PrintWriter(System.out);
	private static class INPUT {

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar, numChars;

		public INPUT (InputStream stream) {
			this.stream = stream;
		}

		public INPUT (String file) throws IOException {
			this.stream = new FileInputStream (file);
		}

		public int cscan () throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read (buf);
			}
			
			if (numChars == -1)
				return numChars;

			return buf[curChar++];
		}

		public int iscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();

			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}

			int res = 0;

			do {
				res = (res << 1) + (res << 3);
				res += c - '0';
				c = cscan ();
			}
			while (!space (c));

			return res * sgn;
		}

		public String sscan () throws IOException {
			int c = cscan ();
			
			while (space (c))
				c = cscan ();

			StringBuilder res = new StringBuilder ();

			do {
				res.appendCodePoint (c);
				c = cscan ();
			}
			while (!space (c));

			return res.toString ();
		}

		public double dscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();

			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}

			double res = 0;

			while (!space (c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * UTILITIES.fast_pow (10, iscan ());
				
				res *= 10;
				res += c - '0';
				c = cscan ();
			}

			if (c == '.') {
				c = cscan ();
				double m = 1;

				while (!space (c)) {
					if (c == 'e' || c == 'E')
						return res * UTILITIES.fast_pow (10, iscan ());

					m /= 10;
					res += (c - '0') * m;
					c = cscan ();
				}
			}

			return res * sgn;
		}

		public long lscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();

			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}

			long res = 0;

			do {
				res = (res << 1) + (res << 3);
				res += c - '0';
				c = cscan ();
			}
			while (!space (c));

			return res * sgn;
		}

		public boolean space (int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

	public static class UTILITIES {

		static final double EPS = 10e-6;

		public static int lower_bound (int[] arr, int x) {
			int low = 0, high = arr.length, mid = -1;

			while (low < high) {
				mid = (low + high) / 2;

				if (arr[mid] >= x)
					high = mid;
				else
					low = mid + 1;
			}

			return low;
		}

		public static int upper_bound (int[] arr, int x) {
			int low = 0, high = arr.length, mid = -1;

			while (low < high) {
				mid = (low + high) / 2;

				if (arr[mid] > x)
					high = mid;
				else
					low = mid + 1;
			}

			return low;
		}

		public static int gcd (int a, int b) {
			return b == 0 ? a : gcd (b, a % b);
		}

		public static int lcm (int a, int b) {
			return a * b / gcd (a, b);
		}

		public static long fast_pow_mod (long b, long x, int mod) {
			if (x == 0) return 1;
			if (x == 1) return b;
			if (x % 2 == 0) return fast_pow_mod (b * b % mod, x / 2, mod) % mod;

			return b * fast_pow_mod (b * b % mod, x / 2, mod) % mod;
		}

		public static int fast_pow (int b, int x) {
			if (x == 0) return 1;
			if (x == 1) return b;
			if (x % 2 == 0) return fast_pow (b * b, x / 2);

			return b * fast_pow (b * b, x / 2);
		}

		public static long choose (long n, long k) {
			k = Math.min (k, n - k);
			long val = 1;

			for (int i = 0; i < k; ++i)
				val = val * (n - i) / (i + 1);

			return val;
		}

		public static long permute (int n, int k) {
			if (n < k) return 0;
			long val = 1;

			for (int i = 0; i < k; ++i)
				val = (val * (n - i));

			return val;
		}
	}
}