Given a connected undirected graph with $n$ vertices and an integer $k$, you have to either:  either find an independent set that has exactly $\lceil\frac{k}{2}\rceil$ 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 \le k \le n \le 10^5$, $n-1 \le m \le 2 \cdot 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 \le u,v \le 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 $\lceil\frac{k}{2}\rceil$ 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:

$N$

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:

$A$

Difficulty: interview

Starter code:

Solutions:
import sys
from math import ceil
input = sys.stdin.readline
    
n, m, req = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(m)]
g = [[] for _ in range(n + 1)]
for u, v in e:
    g[u].append(v)
    g[v].append(u)
    
# req = 1
# while req * req < n:
#     req += 1
    
def dfs():
    dep = [0] * (n + 1)
    par = [0] * (n + 1)
    st = [1]
    st2 = []
    while st:
        u = st.pop()
        if dep[u]:
            continue
        st2.append(u)
        dep[u] = dep[par[u]] + 1
        for v in g[u]:
            if not dep[v]:
                par[v] = u
                st.append(v)
            elif 2 < dep[u] - dep[v] + 1 <= req:
                cyc = []
                while u != par[v]:
                    cyc.append(u)
                    u = par[u]
                return (None, cyc)
    mk = [0] * (n + 1)
    iset = []
    while st2:
        u = st2.pop()
        if not mk[u]:
            iset.append(u)
            for v in g[u]:
                mk[v] = 1
    return (iset[:ceil(req/2)], None)
    
iset, cyc = dfs()
if iset:
    print(1)
    print(*iset)
else:
    print(2)
    print(len(cyc))
    print(*cyc)

from sys import exit,stdin,stderr
def rl():
    return [int(w) for w in stdin.readline().split()]

n, m, k = rl()
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = rl()
    adj[u].append(v)
    adj[v].append(u)

layers = [[] for depth in range(k)]
position = [None for _ in range(n + 1)]
layers[0] = [1]
position[1] = (0, None)
for depth in range(1, k):
    for parent in layers[depth - 1]:
        _, gp = position[parent]
        for child in adj[parent]:
            if child == gp:
                continue
            if position[child]:
                depth2, parent2 = position[child]
                path1 = []
                while depth > depth2:
                    path1.append(parent)
                    depth, parent = position[parent]
                path2 = []
                while parent != parent2:
                    path1.append(parent)
                    path2.append(parent2)
                    depth, parent = position[parent]
                    depth2, parent2 = position[parent2]
                path2.reverse()
                path = path1 + [parent] + path2 + [child]
                if len(path) <= k:
                    print(2)
                    print(len(path))
                    print(*path)
                else:
                    print(1)
                    print(*path[:k:2])
                return
            layers[depth].append(child)
            position[child] = depth, parent

print(1)
if layers[k - 1]:
    print(*(layer[0] for layer in layers[::2]))
else:
    k2 = (k + 1) // 2
    r = [[], []]
    for depth, layer in enumerate(layers):
        ri = r[depth % 2]
        ri += layer
        if len(ri) >= k2:
            print(*ri[:k2])
            break


import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):
	"""docstring for Graph"""
	def __init__(self,n,d): # Number of nodes and d is True if directed
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d
		
	def addEdge(self,x,y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root): # NORMAL BFS
		queue = [root]
		queue = deque(queue)
		vis = [0]*self.n
		while len(queue)!=0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i]==0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1

	def dfs(self, root, ans): # Iterative DFS
		stack=[root]
		vis=[0]*self.n
		stack2=[]
		while len(stack)!=0: # INITIAL TRAVERSAL
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i]==0:
					self.parent[i] = element
					stack.append(i)

		while len(stack2)!=0: # BACKTRACING. Modify the loop according to the question
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i!=self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest): # Calculate Shortest Path between two nodes
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]]!=-1:
			path.append(parent[path[-1]])
		return path[::-1]

	def ifcycle(self):
		queue = [0]
		vis = [0]*n
		queue = deque(queue)
		while len(queue)!=0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i]==1 and i!=self.parent[element]:
					s = i
					e = element
					path1 = [s]
					path2 = [e]
					while self.parent[s]!=-1:
						s = self.parent[s]
						path1.append(s)
					while self.parent[e]!=-1:
						e = self.parent[e]
						path2.append(e)
					for i in range(-1,max(-len(path1),-len(path2))-1,-1):
						if path1[i]!=path2[i]:
							return path1[0:i+1]+path2[i+1::-1]
				if vis[i]==0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1
		return -1

	def reroot(self, root, ans):
		stack = [root]
		vis = [0]*n
		while len(stack)!=0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				# Reverse_The_Change()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e]==-1:
				continue
			# Change_The_Answers()

	def dfss(self, root):

		vis=[0]*self.n
		color=[-1]*self.n
		color[root]=0
		# self.pdfs(root,vis,color)
		# return
		stack=[root]
		while len(stack)!=0:
			e=stack.pop()
			if vis[e]:
				continue

			if color[e]==-1:
				if color[self.parent[e]]:
					color[e]=0
					g1.append(e+1)
				else:
					color[e]=1
					g2.append(e+1)
			vis[e]=1

			for i in self.graph[e]:
				if not vis[i]:
					stack.append(i)
					self.parent[i]=e

		return

n,m,k = list(map(int,input().split()))
g = Graph(n,False)
for i in range(m):
	a,b = list(map(int,input().split()))
	g.addEdge(a-1,b-1)
l = g.ifcycle()
# print (l)
if l!=-1 and len(l)<=k:
	print(2)
	print(len(l))
	for i in range(len(l)):
		l[i] += 1
	print(*l)
	return
g1,g2 = [1],[]
g.dfss(0)
if len(g1)>=(k-1)//2+1:
	print(1)
	print(*g1[0:(k-1)//2+1])
else:
	print(1)
	print(*g2[0:(k-1)//2+1])