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$

Source: codeforces | Difficulty: MEDIUM


Solutions:
import io
import os
from collections import Counter, defaultdict, deque
import sys
sys.setrecursionlimit(10 ** 5 + 1)
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def bfs(g, source):
	q = deque()
	dist = {}
	q.append(source)
	dist[source] = 0
	while q:
		node = q.popleft()
		assert node in dist
		d = dist[node]
		for nbr in g[node]:
			if nbr not in dist:
				q.append(nbr)
				dist[nbr] = d + 1
	return dist

def findCycle(source, graph):

	@bootstrap
	def f(path, depth):
		cycleDepth = -1
		for nbr in graph[path[-1]]:
			if len(path) >= 2 and nbr == path[-2]:
				continue
			if nbr in depth:
				cycleDepth = max(cycleDepth, depth[nbr])
		if cycleDepth != -1:
			yield path[cycleDepth:]
			return
		for nbr in graph[path[-1]]:
			if len(path) >= 2 and nbr == path[-2]:
				continue
			depth[nbr] = depth[path[-1]] + 1
			path.append(nbr)
			ret = (yield f(path, depth))
			if ret:
				yield ret
				return
			path.pop()
			del depth[nbr]
		yield None
		return
	return f([source], {source: 0})

def solve(N, M, K, edges):
	graph = [[] for i in range(N)]
	for (u, v) in edges:
		graph[u].append(v)
		graph[v].append(u)
	cycle = findCycle(0, graph)
	independentLen = (K + 1) // 2
	if cycle:
		if len(cycle) <= K:
			ans = cycle
			return '2' + '\n' + str(len(ans)) + '\n' + ' '.join((str(x + 1) for x in ans))
		else:
			ans = []
			for i in range(independentLen):
				ans.append(cycle[i * 2])
			return '1' + '\n' + ' '.join((str(x + 1) for x in ans))
	else:
		dist = bfs(graph, 0)
		evenCount = 0
		oddCount = 0
		for (v, d) in dist.items():
			if d % 2 == 0:
				evenCount += 1
			else:
				oddCount += 1
		mod = 0
		if evenCount >= independentLen:
			mod = 0
		elif oddCount >= independentLen:
			mod = 1
		else:
			return -1
		ans = []
		for (v, d) in dist.items():
			if d % 2 == mod:
				ans.append(v)
				if len(ans) == independentLen:
					break
		return '1' + '\n' + ' '.join((str(x + 1) for x in ans))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M, K) = [int(x) for x in input().split()]
edges = [[int(x) - 1 for x in input().split()] for i in range(M)]
ans = solve(N, M, K, edges)
print(ans)


import io
import os
from collections import deque

def bfs(g, source):
	q = deque([source])
	dist = {source: 0}
	while q:
		node = q.popleft()
		assert node in dist
		d = dist[node]
		for nbr in g[node]:
			if nbr not in dist:
				q.append(nbr)
				dist[nbr] = d + 1
	return dist

def findCycle(source, getNbr):
	q = deque([source])
	parent = {source: None}
	dist = {source: 0}
	while q:
		node = q.popleft()
		d = dist[node]
		for nbr in getNbr(node):
			if nbr not in dist:
				q.append(nbr)
				dist[nbr] = d + 1
				parent[nbr] = node
			else:
				if dist[nbr] == d - 1:
					assert nbr == parent[node]
					continue
				assert dist[nbr] in [d, d + 1]
				path1 = [nbr]
				path2 = [node]
				while path1[-1] != path2[-1]:
					if dist[path1[-1]] >= dist[path2[-1]]:
						path1.append(parent[path1[-1]])
					else:
						path2.append(parent[path2[-1]])
				assert path1[-1] == path2[-1]
				path2.pop()
				return path1 + path2[::-1]
	return None

def solve(N, M, K, edges):
	graph = [[] for i in range(N)]
	for (u, v) in edges:
		graph[u].append(v)
		graph[v].append(u)

	def getNbr(u):
		return graph[u]
	cycle = findCycle(0, getNbr)
	independentLen = (K + 1) // 2
	if cycle:
		if len(cycle) <= K:
			ans = cycle
			return '2' + '\n' + str(len(ans)) + '\n' + ' '.join((str(x + 1) for x in ans))
		else:
			ans = []
			for i in range(independentLen):
				ans.append(cycle[i * 2])
			return '1' + '\n' + ' '.join((str(x + 1) for x in ans))
	else:
		dist = bfs(graph, 0)
		evenCount = 0
		oddCount = 0
		for (v, d) in dist.items():
			if d % 2 == 0:
				evenCount += 1
			else:
				oddCount += 1
		mod = 0
		if evenCount >= independentLen:
			mod = 0
		elif oddCount >= independentLen:
			mod = 1
		else:
			return -1
		ans = []
		for (v, d) in dist.items():
			if d % 2 == mod:
				ans.append(v)
				if len(ans) == independentLen:
					break
		return '1' + '\n' + ' '.join((str(x + 1) for x in ans))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M, K) = [int(x) for x in input().split()]
edges = [[int(x) - 1 for x in input().split()] for i in range(M)]
ans = solve(N, M, K, edges)
print(ans)


L = [0] * 200005
O = [0] * 200005
F = [0] * 200005
C = []
czy = 0
W = [[] for _ in range(4)]
P = [[] for _ in range(200005)]
ile = 0

def dfs(n, p):
	stos = []
	stos.append((n, p))
	global czy
	while len(stos) > 0:
		(n, p) = stos[-1]
		stos.pop()
		if O[n] == 1:
			continue
		O[n] = 1
		if L[n] <= k - 1:
			W[L[n] % 2].append(n)
		for v in P[n]:
			if O[v] == 0:
				L[v] = L[n] + 1
				F[v] = n
				stos.append((v, n))
			elif v != p and czy == 0 and (L[n] > L[v]) and (L[n] - L[v] + 1 <= k):
				czy = 1
				x = n
				while x != v:
					C.append(x)
					x = F[x]
				C.append(v)
(n, m, k) = map(int, input().split())
for i in range(m):
	(a, b) = map(int, input().split())
	P[a].append(b)
	P[b].append(a)
dfs(1, 0)
if czy:
	print(2)
	print(len(C))
	print(' '.join(map(str, C)))
else:
	print(1)
	A = []
	if len(W[0]) < len(W[1]):
		A = W[1]
	else:
		A = W[0]
	x = k // 2
	if k & 1:
		x += 1
	s = ''
	for i in range(0, x):
		s += str(A[i]) + ' '
	print(s)


import math
import sys
input = sys.stdin.readline
from collections import *

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]

def dfs():
	global req
	dep = [0] * (n + 1)
	par = [0] * (n + 1)
	st = [5]
	st2 = []
	while st:
		u = st.pop()
		if dep[u]:
			continue
		st2.append(u)
		dep[u] = dep[par[u]] + 1
		for v in g2[u]:
			if not dep[v]:
				par[v] = u
				st.append(v)
			elif dep[u] - dep[v] + 1 >= req:
				cyc = []
				while u != par[v]:
					cyc.append(u)
					u = par[u]
				return (None, cyc)
g = defaultdict(set)
g2 = defaultdict(set)
(n, m) = li()
for i in range(m):
	(a, b) = li()
	g[a].add(b)
	g[b].add(a)
	g2[a].add(b)
	g2[b].add(a)
for i in g2:
	g2[i] = set(sorted(list(g2[i])))
currset = set()
ma = math.ceil(n ** 0.5)
req = ma
for i in sorted(g, key=lambda x: len(g[x])):
	if i in g:
		currset.add(i)
		for k in list(g[i]):
			if k in g:
				g.pop(k)
		g.pop(i)
	if len(currset) == ma:
		break
if len(currset) >= ma:
	print(1)
	print(*list(currset)[:ma])
	exit()
print(2)
(_, cycles) = dfs()
print(len(cycles))
print(*cycles)


from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def dfs():
	parent = [0] * (n + 1)
	stk = [4]
	depth = [0] * (n + 1)
	while len(stk) > 0:
		node = stk.pop()
		if depth[node] != 0:
			continue
		depth[node] = depth[parent[node]] + 1
		for nd in gdup[node]:
			if depth[nd] == 0:
				stk.append(nd)
				parent[nd] = node
			elif depth[node] - depth[nd] + 1 >= want:
				cycle = [nd]
				curr = node
				while curr != nd:
					cycle.append(curr)
					curr = parent[curr]
				return cycle
(n, m) = rinput()
gdup = defaultdict(list)
want = int(math.ceil(math.sqrt(n)))
for _ in range(m):
	(u, v) = rinput()
	gdup[u].append(v)
	gdup[v].append(u)
flag = False
independent = set()
setlen = 0
temp = sorted(gdup, key=lambda x: len(gdup[x]))
visited = [False] * (n + 1)
for i in temp:
	if not visited[i]:
		independent.add(i)
		setlen += 1
		if setlen == want:
			flag = True
			break
		visited[i] = True
		for nd in gdup[i]:
			visited[nd] = True
if flag:
	print(1)
	print(*independent)
if not flag:
	cycle = dfs()
	print(2)
	print(len(cycle))
	print(*cycle)


import math
import collections
from collections import defaultdict
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(root):
	stack = [root]
	par = {}
	par[root] = 0
	while stack:
		vertex = stack.pop()
		dist[vertex] = dist[par[vertex]] + 1
		for neighbour in graph[vertex]:
			if neighbour == par[vertex]:
				continue
			if dist[neighbour] == 0:
				par[neighbour] = vertex
				stack.append(neighbour)
			elif dist[neighbour] < dist[vertex]:
				return (True, restore(par, vertex, neighbour))
	return (False, dist)

def restore(par, neigh, vertex):
	res = []
	while neigh != vertex:
		res.append(neigh)
		neigh = par[neigh]
	res.append(neigh)
	return res
(n, m, k) = map(int, input().split())
dist = [0] * (n + 1)
graph = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	if u <= k and v <= k:
		graph[u].append(v)
		graph[v].append(u)
for i in range(1, k + 1):
	if dist[i]:
		continue
	(b, arr) = bfs(i)
	if b == True:
		break
if b == True:
	print(2)
	print(len(arr))
	print(*arr)
else:
	print(1)
	(odd, even) = ([], [])
	for i in range(1, k + 1):
		if arr[i] & 1:
			odd.append(i)
		else:
			even.append(i)
	if len(odd) > len(even):
		(odd, even) = (even, odd)
	for i in range((k + 1) // 2):
		print(even[i], end=' ')


from typing import List
import sys
input = sys.stdin.readline
import math

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().strip().split())

def from_file(f):
	return f.readline

def solve_tree(n, m, k, edges):
	color = [-1] * n
	stack = [0]
	c = [1, 0]
	color[0] = 0
	while stack:
		cur = stack.pop()
		for u in edges[cur]:
			if color[u] != -1:
				continue
			new_col = 1 - color[cur]
			color[u] = new_col
			c[new_col] += 1
			stack.append(u)
	max_col = 0
	if c[0] < c[1]:
		max_col = 1
	verts = [i + 1 for i in range(n) if color[i] == max_col][:(k + 1) // 2]
	print('1')
	print(' '.join(map(str, verts)))

def solve_cycle(n, k, edges):
	(WHITE, GREY, BLACK) = (0, 1, 2)
	t = [-1] * n
	stack = [0]
	color = [WHITE] * n
	parent = [None] * n
	color[0] = GREY
	next_time = 0
	while stack:
		cur = stack.pop()
		col = color[cur]
		if col == BLACK:
			continue
		color[cur] = BLACK
		t[cur] = next_time
		next_time += 1
		stack.append(cur)
		maxt = -1
		v_back = None
		for v in edges[cur]:
			if color[v] == BLACK and parent[cur] != v:
				if t[v] > maxt:
					maxt = t[v]
					v_back = v
			elif color[v] != BLACK:
				stack.append(v)
				color[v] = GREY
				parent[v] = cur
		if maxt != -1:
			(task, verts) = process_cycle(v_back, cur, parent, k)
			break
	print(task)
	if task == 2:
		print(len(verts))
	print(' '.join(map(str, verts)))

def process_cycle(v_back: int, cur: int, parent: List[int], k: int):
	cycle = [cur + 1]
	while cur != v_back:
		cur = parent[cur]
		cycle.append(cur + 1)
	if len(cycle) <= k:
		return (2, cycle)
	else:
		ind_set = cycle[0::2][:(k + 1) // 2]
		return (1, ind_set)

def solve(n, m, k, edges):
	if m == n - 1:
		solve_tree(n, m, k, edges)
		return
	solve_cycle(n, k, edges)
(n, m, k) = invr()
edges = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = invr()
	edges[u - 1].append(v - 1)
	edges[v - 1].append(u - 1)
solve(n, m, k, edges)


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
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)

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)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def dfs(u):
	stack = [(u, -1, 0)]
	while stack:
		(u, pu, c) = stack.pop()
		par[u] = pu
		color[u] = c
		for v in to[u]:
			if v == pu:
				continue
			if par[v] == -1:
				stack.append((v, u, 1 - c))
			else:
				par[v] = u
				return u
	return -1
(n, m, k) = MI()
to = [[] for _ in range(k)]
for _ in range(m):
	(u, v) = MI1()
	if u < k and v < k:
		to[u].append(v)
		to[v].append(u)
par = [-1] * k
color = [-1] * k
ans = []
for u in range(k):
	if par[u] != -1:
		continue
	s = dfs(u)
	if s != -1:
		v = s
		while 1:
			ans.append(v + 1)
			v = par[v]
			if v == s:
				break
		print(2)
		print(len(ans))
		print(*ans)
		exit()
c = (color.count(1) * 2 >= k) * 1
for u in range(k):
	if color[u] == c:
		ans.append(u + 1)
	if len(ans) == (k + 1) // 2:
		break
print(1)
print(*ans)


import sys
(n, m) = sys.stdin.readline().strip().split(' ')
n = int(n)
m = int(m)
part = int((n - 1) ** 0.5 + 1)
d = {}
e = {}
for i in range(m):
	(x, y) = sys.stdin.readline().strip().split(' ')
	y = int(y)
	x = int(x)
	if x not in e:
		e[x] = []
	if y not in e:
		e[y] = []
	e[x].append(y)
	e[y].append(x)
stack_queue = []
stack_queue.append((1, 0, -1, 0, 0))
tp = 0
res = []
cnt = {}
while len(stack_queue) > 0:
	now = stack_queue.pop()
	(x, h, fa, r, idone) = now
	if x not in d:
		d[x] = h
		tmpp = h % (part - 1)
		cnt[tmpp] = cnt.get(tmpp, 0) + 1
	if r == 0:
		for i1 in range(idone, len(e[x])):
			i = e[x][i1]
			if fa == i:
				continue
			if i in d:
				if d[x] - d[i] + 1 >= part:
					tp = i
					res.append(str(x))
					break
				else:
					continue
			stack_queue.append((x, h, fa, 1, i1))
			if tp == 0:
				stack_queue.append((i, h + 1, x, 0, 0))
			break
		continue
	if r == 1:
		i = e[x][idone]
		if tp > 0:
			res.append(str(x))
			if x == tp:
				tp = -1
		if tp == 0:
			stack_queue.append((x, h, fa, 0, idone + 1))
if len(res) > 0:
	print(2)
	print(len(res))
	print(' '.join(res))
else:
	target = -1
	for i in cnt:
		if cnt[i] >= part:
			target = i
			break
	tmppart = part
	for i in d:
		if d[i] % (tmppart - 1) != target:
			continue
		if part > 0:
			part -= 1
			res.append(str(i))
		else:
			break
	print(1)
	print(' '.join(res))


import sys
input = sys.stdin.readline
import heapq
import copy
import math
import decimal

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def insr2():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())

def pr_list(a):
	print(*a, sep=' ')

def main():
	tests = 1
	mod = 998244353
	limit = 10 ** 18
	ans = 0
	for test in range(tests):
		[n, m, k] = inlt()
		adj = [{} for i in range(n + 1)]
		for i in range(m):
			[u, v] = inlt()
			adj[u][v] = 1
			adj[v][u] = 1
		done = [0 for i in range(n + 1)]
		s_hash = {}
		s_hash[1] = 1
		done[1] = 1
		stack = [1]
		is_cycle = 0
		found = 0
		token0 = {}
		token1 = {}
		token0[1] = 1
		while stack != []:
			curr = stack[-1]
			to_pop = 1
			for i in adj[curr]:
				if curr in token0:
					token1[i] = 1
				else:
					token0[i] = 1
				if i in s_hash and stack[-2] != i:
					is_cycle = 1
					for j in range(len(stack)):
						if stack[j] == i:
							cycle = stack[j:len(stack)]
							break
					break
			if is_cycle == 1:
				break
			if len(stack) >= k and stack[0] not in adj[stack[-1]]:
				found = 1
				break
			for i in adj[curr]:
				if done[i] != 1:
					stack.append(i)
					done[i] = 1
					s_hash[i] = 1
					to_pop = 0
					break
			if to_pop == 1:
				del s_hash[curr]
				stack.pop()
		if is_cycle == 1:
			print(2)
			print(len(cycle))
			pr_list(cycle)
			continue
		elif found == 1:
			ans = []
			for i in range(len(stack)):
				if i % 2 == 0:
					ans.append(stack[i])
			print(1)
			pr_list(ans[0:math.ceil(k / 2)])
			continue
		ans = []
		if len(token1) > len(token0):
			maxi = token1
		else:
			maxi = token0
		for i in maxi:
			ans.append(i)
			if len(ans) >= k:
				break
		print(1)
		pr_list(ans[0:math.ceil(k / 2)])
main()


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

class Graph(object):

	def __init__(self, n, d):
		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):
		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):
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			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:
			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):
		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()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue

	def dfss(self, root):
		vis = [0] * self.n
		color = [-1] * self.n
		color[root] = 0
		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) = map(int, input().split())
g = Graph(n, False)
for i in range(m):
	(a, b) = map(int, input().split())
	g.addEdge(a - 1, b - 1)
l = g.ifcycle()
if l != -1 and len(l) <= k:
	print(2)
	print(len(l))
	for i in range(len(l)):
		l[i] += 1
	print(*l)
	exit()
(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])


from sys import stdin, stdout, setrecursionlimit
import threading
threading.stack_size(2 ** 26)
setrecursionlimit(10 ** 9)
line1 = [int(x) for x in stdin.readline().split()]
vertexes = line1[0]
edges = line1[1]
k = line1[2]
ceiling = k // 2 if k % 2 == 0 else (k + 1) // 2
graph = [[] for _ in range(vertexes + 1)]
parents = [-1 for _ in range(vertexes + 1)]
visited = [0 for _ in range(vertexes + 1)]
depth = [0 for _ in range(vertexes + 1)]
sets = [[] for _ in range(2)]
while edges > 0:
	line1 = [int(x) for x in stdin.readline().split()]
	edges -= 1
	graph[line1[0]].append(line1[1])
	graph[line1[1]].append(line1[0])

def DFS_Cycle_Visit(vertex):
	visited[vertex] = 1
	if depth[vertex] < k:
		sets[depth[vertex] % 2].append(vertex)
	for ady in graph[vertex]:
		if visited[ady] == 0:
			parents[ady] = vertex
			depth[ady] = depth[vertex] + 1
			DFS_Cycle_Visit(ady)
		else:
			current_length = depth[vertex] - depth[ady] + 1
			if 3 <= current_length <= k:
				stdout.write('2\n')
				cycle = []
				i = vertex
				while i != ady:
					cycle.append(i)
					i = parents[i]
				cycle.append(ady)
				stdout.write('{}\n'.format(len(cycle)))
				for elem in range(len(cycle) - 1, -1, -1):
					stdout.write('{} '.format(cycle[elem]))
				exit(0)

def DFS_Cycle():
	for vertex in range(1, len(graph)):
		if visited[vertex] == 0:
			DFS_Cycle_Visit(vertex)
	stdout.write('1\n')
	bigger_set = sets[0] if len(sets[0]) >= len(sets[1]) else sets[1]
	for elem in range(0, ceiling):
		stdout.write('{} '.format(bigger_set[elem]))
threading.Thread(target=DFS_Cycle).start()


import sys
input = sys.stdin.buffer.readline
INF = 10 ** 18
(N, M, K) = map(int, input().split())
graph = [[] for _ in range(K)]
for _ in range(M):
	(a, b) = map(int, input().split())
	if a <= K and b <= K:
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
ans = []
D = [-1] * K
Par = [-1] * K
iscycle = INF
stop = INF
for s in range(K):
	if D[s] != -1:
		continue
	D[s] = 0
	stack = [s]
	dp = [[s], []]
	while stack and iscycle == INF:
		p = stack.pop()
		for np in graph[p]:
			if D[np] == -1:
				Par[np] = p
				D[np] = D[p] + 1
				stack.append(np)
				dp[D[np] % 2].append(np)
			elif (D[p] - D[np] + 1) % 2 != 0:
				stop = Par[np]
				Par[np] = p
				iscycle = np
				break
	if iscycle != INF:
		break
	if len(dp[0]) > len(dp[1]):
		for p in dp[0]:
			ans.append(p + 1)
	else:
		for p in dp[1]:
			ans.append(p + 1)
if iscycle == INF:
	ans = ans[:(K + 1) // 2]
	print(1)
	print(*ans)
else:
	ans = [stop + 1]
	s = iscycle
	while s != stop:
		ans.append(s + 1)
		s = Par[s]
	print(2)
	print(len(ans))
	print(*ans)


from types import GeneratorType
from sys import stdin, stdout
import math

def input():
	return stdin.readline().strip()

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

class Graph:
	WHITE = 0
	GREY = 1
	BLACK = 2

	def __init__(self, N):
		self.colours = dict()
		self.neighbours = dict()
		for v in range(1, N + 1):
			self.neighbours[v] = set()
			self.colours[v] = Graph.WHITE

	@classmethod
	def line(self, N):
		g = Graph(N)
		for i in range(1, N):
			g.add_edge(i, i + 1)
		return g

	def add_edge(self, u, v):
		self.neighbours[u].add(v)
		self.neighbours[v].add(u)

	def uncontractable_cycle(self):
		self.levels = dict()
		self.parent_of = dict()
		return self._uncontractable_cycle(1, 1, 0)

	@bootstrap
	def _uncontractable_cycle(self, parent, u, level):
		self.levels[u] = level
		self.colours[u] = Graph.GREY
		self.parent_of[u] = parent
		back_edges = []
		for v in self.neighbours[u]:
			if v == parent:
				continue
			if self.colours[v] == Graph.GREY:
				back_edges += [(self.levels[u] - self.levels[v], (u, v))]
		if len(back_edges):
			(_, (u, v)) = sorted(back_edges)[0]
			cycle = [u]
			while True:
				if cycle[-1] == v:
					break
				cycle += [self.parent_of[cycle[-1]]]
			yield cycle
			return
		for v in self.neighbours[u]:
			if v == parent:
				continue
			if self.colours[v] == Graph.WHITE:
				r = (yield self._uncontractable_cycle(u, v, level + 1))
				if r is not None:
					yield r
			else:
				continue
		self.colours[u] = Graph.BLACK
		yield None

def ans(g, N, K):
	cycle = g.uncontractable_cycle()
	if cycle is not None:
		if len(cycle) <= K:
			cycle = cycle[::-1]
			print(2)
			print(len(cycle))
			print(' '.join(map(str, cycle)))
		else:
			IS = []
			for (i, e) in enumerate(cycle):
				if i % 2 == 1:
					IS += [e]
			IS = IS[0:math.ceil(K / 2)]
			print(1)
			print(' '.join(map(str, IS)))
		return
	is0 = []
	is1 = []
	for i in range(1, N + 1):
		if g.levels[i] % 2 == 0:
			is0 += [i]
		else:
			is1 += [i]
	if len(is0) >= math.ceil(K / 2):
		IS = is0
	else:
		IS = is1
	IS = IS[0:math.ceil(K / 2)]
	print(1)
	print(' '.join(map(str, IS)))
(N, M, K) = input().split(' ')
N = int(N)
M = int(M)
K = int(K)
g = Graph(N)
for _ in range(M):
	(u, v) = input().split(' ')
	u = int(u)
	v = int(v)
	g.add_edge(u, v)
ans(g, N, K)


from collections import defaultdict
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
sys.setrecursionlimit(10 ** 2)

def print_case_iterable(case_num, iterable):
	print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
	print('Case #{}: {}'.format(case_num, iterable))

def print_iterable(A):
	print(' '.join(A))

def read_int():
	return int(f.readline().strip())

def read_int_array():
	return [int(x) for x in f.readline().strip().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def read_string():
	return list(f.readline().strip())

def ri():
	return int(f.readline().strip())

def ria():
	return [int(x) for x in f.readline().strip().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def rs():
	return list(f.readline().strip())

def bi(x):
	return bin(x)[2:]
from collections import deque
import math
NUMBER = 998244353

def factorial(n):
	M = NUMBER
	f = 1
	for i in range(1, n + 1):
		f = f * i % M
	return f

def mult(a, b):
	return a * b % NUMBER

def minus(a, b):
	return (a - b) % NUMBER

def plus(a, b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a):
	m = NUMBER
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	if n < k:
		assert false
	return mult(factorial(n), modinv(mult(factorial(k), factorial(n - k))))
from collections import deque, defaultdict
import heapq

def bfs(V, E, k):
	s = set()
	evens = set()
	odds = set()
	parents = defaultdict(int)
	depths = defaultdict(int)
	v = 1
	q = deque([])
	s.add(v)
	q.append((v, None, 0))
	parents[1] = 0
	inds = (k + 1) // 2
	while len(q) > 0:
		(x, parent, depth) = q.popleft()
		if depth % 2 == 0:
			evens.add(x)
		else:
			odds.add(x)
		for u in E[x]:
			if u in s and u != parent:
				if depth + 1 + depths[u] <= k:
					return (depths, parents, u, x)
			if u not in s:
				s.add(u)
				q.append((u, x, depth + 1))
				parents[u] = x
				depths[u] = depth + 1
		if len(evens) >= inds:
			return (evens,)
		if len(odds) >= inds:
			return (odds,)

def solution(V, E, n, m, k):
	res = bfs(V, E, k)
	if len(res) > 1:
		(depths, parents, v, u) = res
		u_path = []
		s = set()
		while u != 0:
			s.add(u)
			u_path.append(u)
			u = parents[u]
		v_path = []
		while v != 0 and v not in s:
			v_path.append(v)
			v = parents[v]
		u_path = list(reversed(u_path))
		for i in range(len(u_path)):
			if u_path[i] == v:
				break
		u_path = u_path[i:]
		sol = u_path + v_path
		return '2\n' + str(len(sol)) + '\n' + ' '.join(map(str, sol))
	else:
		s = list(res[0])[:(k + 1) // 2]
		return '1\n' + ' '.join(map(str, s))

def main():
	T = 1
	for i in range(T):
		(n, m, k) = ria()
		E = defaultdict(list)
		V = set()
		for _ in range(m):
			(u, v) = ria()
			E[u].append(v)
			E[v].append(u)
			V.add(u)
			V.add(v)
		x = solution(V, E, n, m, k)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			(print >> output, str(x))
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()
if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
main()


import math
import sys
from collections import deque
from typing import Deque, Dict, List, Optional, Set, Tuple

def data():
	return sys.stdin.buffer.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(res):
	sys.stdout.write(' '.join(map(str, res)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')

def input_lst():
	return mdata()

def print_out(res):
	outl(res)

class GraphNode:

	def __init__(self, id: int):
		self.id = id
		self.sublings: Deque[GraphNode] = deque()

class Graph:

	def __init__(self, n: int):
		self.n = n
		self.nodes = [GraphNode(x) for x in range(n)]

	def add_edge(self, u: int, v: int):
		self.nodes[u].sublings.append(self.nodes[v])
		self.nodes[v].sublings.append(self.nodes[u])

class GraphTraverse:

	def __init__(self, graph: Graph):
		self.graph = graph
		self.watched_nodes: Set[GraphNode] = set()
		self.nodes_color: Dict[GraphNode, bool] = {}
		self.parent_nodes: Dict[GraphNode, GraphNode] = {}
		self.circle_nodes: Optional[Tuple[GraphNode, GraphNode]] = None

	def runBFS(self):
		root_node = self.graph.nodes[0]
		current_nodes = [root_node]
		self.nodes_color[None] = True
		self.watched_nodes.add(root_node)
		self.parent_nodes[root_node] = None
		next_nodes = set()
		while len(current_nodes):
			node = current_nodes.pop()
			for child_node in node.sublings:
				if child_node == self.parent_nodes[node]:
					continue
				if child_node in self.watched_nodes:
					self.circle_nodes = (node, child_node)
					break
				self.parent_nodes[child_node] = node
				next_nodes.add(child_node)
			if self.circle_nodes is not None:
				break
			self.nodes_color[node] = not self.nodes_color[self.parent_nodes[node]]
			self.watched_nodes.add(node)
			if len(current_nodes) == 0:
				current_nodes = list(next_nodes)
				next_nodes = set()
		del self.nodes_color[None]

	def calc_circle(self):
		if self.circle_nodes is None:
			return
		watched_nodes = set()
		current_node = self.circle_nodes[0]
		while current_node is not None:
			watched_nodes.add(current_node)
			current_node = self.parent_nodes[current_node]
		current_node = self.circle_nodes[1]
		union_node = None
		while current_node is not None:
			if current_node in watched_nodes:
				union_node = current_node
				break
			watched_nodes.add(current_node)
			current_node = self.parent_nodes[current_node]
		circle_nodes_order = deque()
		current_node = self.circle_nodes[0]
		while current_node is not None:
			circle_nodes_order.append(current_node)
			if current_node == union_node:
				break
			current_node = self.parent_nodes[current_node]
		circle_nodes_order2 = deque()
		current_node = self.circle_nodes[1]
		while current_node != union_node:
			circle_nodes_order2.append(current_node)
			current_node = self.parent_nodes[current_node]
		circle_nodes_order2.reverse()
		circle_nodes_order += circle_nodes_order2
		return circle_nodes_order

def main():
	(n, m, k) = input_lst()
	graph = Graph(n)
	for i in range(m):
		(u, v) = input_lst()
		u -= 1
		v -= 1
		graph.add_edge(u, v)
	traverse = GraphTraverse(graph)
	traverse.runBFS()
	if traverse.circle_nodes is not None:
		circle_nodes_order = traverse.calc_circle()
		if len(circle_nodes_order) <= k:
			res = [x.id + 1 for x in circle_nodes_order]
			print_out([2])
			print_out([len(res)])
			print_out(res)
			return
	nodes_count = int(k // 2 + k % 2)
	black_nodes = [k for (k, v) in traverse.nodes_color.items() if not v]
	red_nodes = [k for (k, v) in traverse.nodes_color.items() if v]
	if len(black_nodes) >= nodes_count:
		res = [x.id + 1 for x in black_nodes[:nodes_count]]
	else:
		res = [x.id + 1 for x in red_nodes[:nodes_count]]
	print_out([1])
	print_out(res)
main()


import sys, math
import io, os
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.buffer.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
mod = int(1000000000.0) + 7

def find(x):
	l = []
	s = [x]
	depth = [0] * (n + 1)
	vis = [0] * (n + 1)
	par = [0] * (n + 1)
	d = n + 1
	while s:
		a = s[-1]
		if vis[a] == 1:
			s.pop()
			l.pop()
			vis[a] = 0
			continue
		vis[a] = 1
		l.append(a)
		depth[a] = len(l)
		for j in g[a]:
			if j != par[a]:
				if vis[j] == 1:
					d = depth[j]
					break
				par[j] = a
				s.append(j)
		if d != n + 1:
			break
	return l[d - 1:]
(n, m, k) = mdata()
g = [[] for i in range(n + 1)]
for i in range(m):
	(u, v) = mdata()
	g[u].append(v)
	g[v].append(u)
l = find(1)
if l:
	if len(l) <= k:
		out(2)
		out(len(l))
		outl(l)
	else:
		l = l[::2][:k // 2 + k % 2]
		out(1)
		outl(l)
else:
	v = [0] * (n + 1)
	l = [[1], []]
	s = [1]
	vis = [0] * (n + 1)
	while s:
		a = s.pop()
		vis[a] = 1
		for i in g[a]:
			if vis[i] == 0:
				v[i] = 1 - v[a]
				l[v[i]].append(i)
				s.append(i)
	out(1)
	if len(l[0]) > len(l[1]):
		outl(l[0][:k // 2 + k % 2])
	else:
		outl(l[1][:k // 2 + k % 2])


def main():
	from sys import stdin, stdout
	from array import array
	(n, m, k) = map(int, stdin.readline().split())
	g = [array('i', ()) for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = map(int, stdin.readline().split())
		g[u].append(v)
		g[v].append(u)
	if m == n - 1:
		colors = array('i', (1,)) * (n + 1)
		ans_s = [[], [], []]
		stack = [(1, 1)]
		while stack:
			(u, v) = stack.pop()
			colors[u] = 3 - colors[v]
			ans_s[colors[u]].append(u)
			for w in g[u]:
				if w != v:
					stack.append((w, u))
		ans = max(ans_s, key=len)
	else:
		q = [(1, -1)]
		parents = array('i', (0,)) * (n + 1)
		for (u, v) in q:
			if parents[u]:
				part1 = []
				while u != -1:
					part1.append(u)
					u = parents[u]
				part2 = []
				while v != -1:
					part2.append(v)
					v = parents[v]
				part1.reverse()
				part2.reverse()
				ans1 = []
				ans2 = []
				w2 = 0
				p1i = iter(part1)
				p2i = iter(part2)
				for (u2, v2) in zip(p1i, p2i):
					if u2 != v2:
						ans1.append(u2)
						ans2.append(v2)
						break
					else:
						w2 = u2
				ans1.extend(p1i)
				ans2.extend(p2i)
				ans2.reverse()
				ans = ans1 + ans2
				ans.append(w2)
				if len(ans) <= k:
					print(2)
					print(len(ans))
					print(*ans)
					return
				ans = ans[1::2]
			else:
				parents[u] = v
				for w in g[u]:
					if w != v:
						q.append((w, u))
	print(1)
	print(*ans[:(k + 1) // 2])
main()


import sys
from collections import deque
input = sys.stdin.buffer.readline
(n, m, k) = map(int, input().split())
e = [[] for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	e[a].append(b)
	e[b].append(a)

def get_root():
	q = deque([1])
	par = [0] * (n + 1)
	par[1] = 1
	while q:
		u = q.popleft()
		for v in e[u]:
			if v == par[u]:
				continue
			if par[v] > 0:
				return u
			else:
				par[v] = u
				q.append(v)
	return 1
root = get_root()

def print_cycle(u, v, par):
	(up, vp) = ([], [])
	while u != root:
		up.append(u)
		u = par[u]
	while v != root:
		vp.append(v)
		v = par[v]
	cy = up + [root] + list(reversed(vp))
	print(2)
	print(len(cy))
	print(*cy)
	exit()
q = deque([root])
par = [0] * (n + 1)
par[root] = root
dep = [0] * (n + 1)
dep[1] = 1
(col0, col1) = ([], [])
while q:
	u = q.popleft()
	if dep[u] % 2:
		col0.append(u)
	else:
		col1.append(u)
	if len(col0) + len(col1) == k:
		break
	for v in e[u]:
		if v == par[u]:
			continue
		if par[v] > 0:
			if dep[u] + dep[v] - 1 <= k:
				print_cycle(u, v, par)
		else:
			par[v] = u
			dep[v] = dep[u] + 1
			q.append(v)
res = col0 if len(col0) >= len(col1) else col1
res = [res[i] for i in range((k + 1) // 2)]
print(1)
print(*res)


import sys
import math
from collections import defaultdict, deque
import heapq

def get_cycle(st, end, parent, now):
	q = deque()
	parent = [-1 for _ in range(n + 1)]
	q.append([st, 0])
	vis = defaultdict(int)
	vis[st] = 1
	while q:
		(cur, d) = q.popleft()
		if d + 1 >= now:
			return now + 1
		if cur == end:
			return d + 1
		for x in graph[cur]:
			if vis[x] == 0:
				if [min(cur, x), max(cur, x)] != [min(st, end), max(st, end)]:
					vis[x] = 1
					parent[x] = cur
					q.append([x, d + 1])
(n, m, k) = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
for i in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	graph[u].append(v)
	graph[v].append(u)
vis = defaultdict(int)
dis = [-1 for _ in range(n + 1)]
parent = [-1 for _ in range(n + 1)]
q = deque()
cycle = 10000000000.0
st = -1
q.append([1, 0])
dis[1] = 0
parent[1] = -1
vis[1] = 1
end = -1
while q:
	(cur, d) = q.popleft()
	for x in graph[cur]:
		if parent[cur] != x and vis[x] == 1:
			cnt = 0
			(curr, xx) = (cur, x)
			if dis[curr] > dis[xx]:
				while dis[curr] > dis[xx]:
					curr = parent[curr]
					cnt += 1
			if dis[xx] > dis[curr]:
				while dis[xx] > dis[curr]:
					xx = parent[xx]
					cnt += 1
			while xx != curr:
				xx = parent[xx]
				curr = parent[curr]
				cnt += 2
			size = cnt + 1
			if size < cycle:
				cycle = size
				st = x
				end = cur
		if vis[x] == 0:
			q.append([x, d + 1])
			vis[x] = 1
			parent[x] = cur
			dis[x] = d + 1
if cycle != 10000000000.0:
	nodes = []
	parent = [-1 for _ in range(n + 1)]
	q.append(st)
	vis = defaultdict(int)
	vis[st] = 1
	while q:
		cur = q.popleft()
		if cur == end:
			break
		for x in graph[cur]:
			if vis[x] == 0:
				if [min(cur, x), max(cur, x)] != [min(st, end), max(st, end)]:
					vis[x] = 1
					parent[x] = cur
					q.append(x)
	cur = end
	nodes.append(end)
	while cur != st:
		x = parent[cur]
		nodes.append(x)
		cur = x
	if cycle <= k:
		print(2)
		print(cycle)
		print(*nodes)
	else:
		print(1)
		ans = []
		cnt = math.ceil(k / 2)
		for i in range(0, cycle, 2):
			if i >= len(nodes):
				print('Error', cycle, i, len(nodes))
				print(nodes)
			if cnt > 0:
				ans.append(nodes[i])
				cnt -= 1
			else:
				break
		print(*ans)
else:
	cnt = math.ceil(k / 2)
	q = deque()
	q.append([1, True])
	vis = defaultdict(int)
	ans = []
	while q:
		(cur, add) = q.pop()
		for x in graph[cur]:
			if vis[x] == 0:
				vis[x] = 1
				if add and cnt > 0:
					ans.append(x)
					cnt -= 1
				q.append([x, not add])
	if cnt == 0:
		print(1)
		print(*ans)
	else:
		cnt = math.ceil(k / 2)
		q = deque()
		q.append([graph[1][0], True])
		vis = defaultdict(int)
		ans = []
		while q:
			(cur, add) = q.pop()
			for x in graph[cur]:
				if vis[x] == 0:
					vis[x] = 1
					if add and cnt > 0:
						ans.append(x)
						cnt -= 1
					q.append([x, not add])
		print(1)
		print(*ans)


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
target = (k + 1) // 2

def solve(start):
	D = [-1] * n
	D[start] = 0
	P = [-1] * n
	IS = set()
	S = [(start, 0)]
	while S:
		(i, o) = S.pop()
		if o == 0:
			if not any((j in IS for j in adj[i])):
				IS.add(i)
				if len(IS) == target:
					print(1)
					print(' '.join(map(lambda v: str(v + 1), IS)))
					sys.exit(0)
		if o < len(adj[i]):
			S.append((i, o + 1))
			j = adj[i][o]
			if D[j] == -1:
				D[j] = D[i] + 1
				P[j] = i
				S.append((j, 0))
			elif D[i] > D[j]:
				cycl = D[i] - D[j]
				if cycl > 1 and cycl < k:
					C = [i]
					while C[-1] != j:
						i = P[i]
						C.append(i)
					print(2)
					print(len(C))
					print(' '.join(map(lambda v: str(v + 1), C)))
					sys.exit(0)
solve(0)
for j in adj[0]:
	solve(j)
	break


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
neig = [0] * n
lev = [-1] * n
for i in range(n):
	neig[i] = [0]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	neig[a][0] += 1
	neig[b][0] += 1
	neig[a].append(b)
	neig[b].append(a)
cont = True
fin = False
circle = [0, 0]
pred = [-1] * n
cur = 0
x = 0
dx = [-1] * n
dx[x] = 0
levx = [[x]]
i = 0
lev[0] = 0
while cont and len(levx) < k:
	if i == len(levx):
		while cur < n and lev[cur] != -1:
			cur += 1
		if cur == n:
			fin = True
		else:
			levx.append([cur])
			lev[cur] = i
			i += 1
	if fin:
		break
	toad = []
	for v in levx[i]:
		for j in range(1, neig[v][0] + 1):
			u = neig[v][j]
			if dx[u] == -1:
				dx[u] = i + 1
				toad.append(u)
				pred[u] = v
				lev[u] = i + 1
			elif pred[v] != u:
				cont = False
				circle = [u, v]
	if len(toad) > 0:
		levx.append(toad)
	i += 1
if len(levx) >= k or fin:
	print(1)
	if fin:
		goal = (k + 1) // 2
		sol1 = []
		sol2 = []
		i = 0
		while len(sol1) < goal and len(sol2) < goal:
			if i % 2 == 0:
				sol1 += levx[i]
			else:
				sol2 += levx[i]
			i += 1
		sol = sol1
		if len(sol2) >= goal:
			sol = sol2
		sol = sol[0:goal]
		for i in range(goal):
			sol[i] += 1
		print(*sol)
	else:
		sol = []
		for i in range(k):
			if i % 2 == 0:
				sol.append(levx[i][0] + 1)
		print(*sol)
else:
	cor = [circle[1] + 1]
	wrong = [circle[0] + 1]
	left = circle[0]
	right = circle[1]
	while left != right:
		if lev[left] < lev[right]:
			right = pred[right]
			cor.append(right + 1)
		else:
			left = pred[left]
			wrong.append(left + 1)
	wrong.remove(left + 1)
	wrong.reverse()
	cor += wrong
	if len(cor) <= k:
		print(2)
		print(len(cor))
		print(*cor)
	else:
		goal = (k + 1) // 2
		sol = []
		for i in range(k):
			if i % 2 == 0:
				sol.append(cor[i])
		print(1)
		print(*sol)


import sys
input = sys.stdin.buffer.readline
from collections import deque
from math import ceil

def prog():
	(n, m, k) = map(int, input().split())
	adj_list = [[[], 0] for i in range(n + 1)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		adj_list[a][0].append(b)
		adj_list[b][0].append(a)
	cycle_found = False
	visited = set()
	visited_s = set()
	done = set()
	s = deque([1])
	while s:
		curr = s[-1]
		visited.add(curr)
		visited_s.add(curr)
		if curr not in done:
			done.add(curr)
			for neighbor in adj_list[curr][0]:
				if neighbor in visited_s and (len(s) > 1 and neighbor != s[-2]):
					cycle = [neighbor]
					new = s.pop()
					while new != neighbor:
						cycle.append(new)
						new = s.pop()
					if len(cycle) <= k:
						sys.stdout.write('2\n')
						sys.stdout.write(str(len(cycle)) + '\n')
						sys.stdout.write(' '.join(map(str, cycle)) + '\n')
					else:
						output = []
						need = ceil(k / 2)
						idx = 0
						while need:
							output.append(cycle[idx])
							idx += 2
							need -= 1
						sys.stdout.write('1\n')
						sys.stdout.write(' '.join(map(str, output)) + '\n')
					cycle_found = True
					break
		if cycle_found:
			break
		had_neighbor = False
		for i in range(adj_list[curr][1], len(adj_list[curr][0])):
			neighbor = adj_list[curr][0][i]
			if neighbor not in visited:
				s.append(neighbor)
				adj_list[curr][1] = i + 1
				had_neighbor = True
				break
		if not had_neighbor:
			visited_s.remove(s.pop())
	if not cycle_found:
		for i in range(1, n + 1):
			adj_list[i][1] = 0
		first = set([1])
		second = set()
		visited = set()
		s = deque([1])
		while s:
			curr = s[-1]
			visited.add(curr)
			had_neighbor = False
			for i in range(adj_list[curr][1], len(adj_list[curr][0])):
				neighbor = adj_list[curr][0][i]
				if neighbor not in visited:
					s.append(neighbor)
					had_neighbor = True
					adj_list[curr][1] = i + 1
					if curr in first:
						second.add(neighbor)
					else:
						first.add(neighbor)
					break
			if not had_neighbor:
				s.pop()
		need = ceil(k / 2)
		if len(second) > len(first):
			sys.stdout.write('1\n')
			sys.stdout.write(' '.join(map(str, list(second)[:need])))
		else:
			sys.stdout.write('1\n')
			sys.stdout.write(' '.join(map(str, list(first)[:need])))
prog()


import math
(n, m) = [int(x) for x in input().split()]
cons = math.ceil(pow(n, 0.5))
adj_mat = [[] for x in range(n + 1)]
(pre_node, cur_deepth) = ([0] * (n + 1), [0] * (n + 1))
for i in range(m):
	(node1, node2) = [int(x) for x in input().split()]
	adj_mat[node1].append(node2)
	adj_mat[node2].append(node1)
(tmp_rec, deep_path) = ([node1], [])
while tmp_rec != []:
	n1 = tmp_rec.pop()
	if cur_deepth[n1] > 0:
		continue
	deep_path.append(n1)
	cur_deepth[n1] = cur_deepth[pre_node[n1]] + 1
	for n2 in adj_mat[n1]:
		if not cur_deepth[n2]:
			pre_node[n2] = n1
			tmp_rec.append(n2)
		elif cur_deepth[n1] - cur_deepth[n2] + 1 >= cons:
			circle = []
			while n1 != pre_node[n2]:
				circle.append(n1)
				n1 = pre_node[n1]
			if len(circle) >= cons:
				print('2')
				print(len(circle))
				print(' '.join([str(x) for x in circle]))
				exit(0)
cur_deepth = [0] * (n + 1)
tmp_arr = []
while deep_path != []:
	n1 = deep_path.pop()
	if not cur_deepth[n1]:
		tmp_arr.append(n1)
		for n2 in adj_mat[n1]:
			cur_deepth[n2] = 1
print('1')
print(' '.join([str(x) for x in tmp_arr[:cons]]))


from collections import defaultdict
(n, m, k) = list(map(int, input().split()))
graph = defaultdict(list)
for i in range(m):
	(u, v) = list(map(int, input().split()))
	(u, v) = (u - 1, v - 1)
	graph[u].append(v)
	graph[v].append(u)
if m == n - 1:
	vis = [-1 for i in range(n)]
	q = [0]
	vis[0] = 0
	while q != []:
		u = q[0]
		q.pop(0)
		for v in graph[u]:
			if vis[v] == -1:
				vis[v] = 1 ^ vis[u]
				q.append(v)
	x = vis.count(0)
	y = n - x
	ans = []
	if x > y:
		z = 0
	else:
		z = 1
	for i in range(n):
		if vis[i] == z:
			ans.append(i + 1)
	req = k // 2
	req += k % 2
	ans = ans[:req]
	print(1)
	print(*ans)
else:
	vis = [False for i in range(n)]
	par = [-1 for i in range(n)]
	q = [0]
	vis[0] = True
	f = 0
	while q != []:
		u = q[0]
		q.pop(0)
		for v in graph[u]:
			if vis[v] == False:
				vis[v] = True
				par[v] = u
				q.append(v)
			elif par[u] != v:
				f = 1
				(path1, path2) = ([], [])
				cur = u
				while True:
					path1.append(cur + 1)
					cur = par[cur]
					if cur == -1:
						break
				cur = v
				while True:
					path2.append(cur + 1)
					cur = par[cur]
					if cur == -1:
						break
				path2 = path2[-1::-1]
				path1 = path1[-1::-1]
				last = -1
				for j in range(min(len(path1), len(path2))):
					if path1[j] == path2[j]:
						last = path1[j]
					else:
						break
				path1 = path1[j:]
				path2 = path2[j:]
				path1 = path1[-1::-1]
				cycle = path1 + [last] + path2
				break
			if f == 1:
				break
		if f == 1:
			break
	if len(cycle) <= k:
		print(2)
		print(len(cycle))
		print(*cycle)
	else:
		o = len(cycle)
		x = k // 2 + k % 2
		ans = []
		print(1)
		for i in range(0, o, 2):
			ans.append(cycle[i])
		print(*ans[:x])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	(n, m, k) = RL()
	gp = [[] for _ in range(n + 1)]
	for _ in range(m):
		(f, t) = RL()
		gp[f].append(t)
		gp[t].append(f)
	vis = [0] * (n + 1)
	cir = ()
	color = [0] * (n + 1)
	pars = [-1] * (n + 1)

	@bootstrap
	def dfs(node, par=-1, c=0):
		nonlocal cir
		vis[node] = 1
		color[node] = c
		pars[node] = par
		for nex in gp[node]:
			if nex == par:
				continue
			if vis[nex] == 0:
				yield dfs(nex, node, c ^ 1)
			elif vis[nex] == 1:
				cir = (node, nex)
		vis[node] = 2
		yield None
	dfs(1)
	if cir == ():
		bl = color.count(1)
		wr = n - bl
		sel = 1
		if wr > bl:
			sel = 0
		res = []
		for i in range(1, n + 1):
			if color[i] == sel:
				res.append(i)
		print(1)
		print(*res[:1 + k >> 1])
	else:
		(f, t) = cir
		circle = [f]
		while circle[-1] != t:
			circle.append(pars[circle[-1]])
		if len(circle) <= k:
			print(2)
			print(len(circle))
			print(*circle)
		else:
			res = []
			now = 0
			for _ in range(1 + k >> 1):
				res.append(circle[now])
				now += 2
			print(1)
			print(*res)
main()


import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def solve1(n, k, adj):
	color = [-1, 0] + [-1] * n
	group = [[1], []]
	stack = [1]
	while stack:
		v = stack.pop()
		for dest in adj[v]:
			if color[dest] != -1:
				continue
			color[dest] = color[v] ^ 1
			group[color[dest]].append(dest)
			stack.append(dest)
	print(1)
	print(*(group[0][:k + 1 >> 1] if len(group[0]) >= len(group[1]) else group[1][:k + 1 >> 1]))

def solve2(n, k, adj):
	stack = [(1, 0)]
	edge_i = [0] * (n + 1)
	depth = [-1, 0] + [-1] * (n + 1)
	prev = [-1, 0] + [-1] * n
	while stack:
		(v, par) = stack[-1]
		if edge_i[v] == 0:
			(d, u) = (-1, -1)
			for dest in adj[v]:
				if dest != par and depth[dest] != -1:
					if d < depth[dest]:
						(d, u) = (depth[dest], dest)
			if d != -1:
				cycle = [u]
				while v != u:
					cycle.append(v)
					v = prev[v]
				if len(cycle) <= k:
					print(f'2\n{len(cycle)}')
					print(*cycle)
				else:
					print(1)
					print(*cycle[:k:2])
				exit()
		for (ei, dest) in enumerate(adj[v][edge_i[v]:], start=edge_i[v]):
			if dest == par:
				continue
			if prev[dest] == -1:
				prev[dest] = v
				depth[dest] = depth[v] + 1
				edge_i[v] = ei + 1
				stack.append((dest, v))
				break
		else:
			stack.pop()

def main():
	(n, m, k) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for (u, v) in (map(int, input().split()) for _ in range(m)):
		adj[u].append(v)
		adj[v].append(u)
	if n - 1 == m:
		solve1(n, k, adj)
	else:
		solve2(n, k, adj)
main()


from sys import stdin, gettrace
from collections import deque
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def readGraph(n, m):
	adj = [set() for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		adj[u - 1].add(v - 1)
		adj[v - 1].add(u - 1)
	return adj

def main():
	(n, m, k) = map(int, inputi().split())
	adj = readGraph(n, m)
	parent = [-2] + [-1] * (n - 1)
	ordered = []
	q = deque()
	q.append(0)
	depth = [0] * n
	while q:
		c = q.popleft()
		for a in adj[c]:
			if parent[a] != -1 and a != parent[c]:
				b1 = [a]
				b2 = [c]
				while parent[a] != parent[c]:
					da = depth[a]
					dc = depth[c]
					if da >= dc:
						a = parent[a]
						b1.append(a)
					if dc >= da:
						c = parent[c]
						b2.append(c)
				loop = b1 + [parent[a]] + b2[::-1]
				if len(loop) <= k:
					print(2)
					print(len(loop))
					print(' '.join(map(lambda x: str(x + 1), loop)))
				else:
					print(1)
					print(' '.join(map(lambda x: str(x + 1), loop[0:k:2])))
				return
			elif parent[a] == -1:
				parent[a] = c
				q.append(a)
				depth[a] = depth[c] + 1
	g0 = [a for a in range(n) if depth[a] % 2 == 0]
	g1 = [a for a in range(n) if depth[a] % 2 == 1]
	if len(g0) >= (k + 1) // 2:
		g = g0
	else:
		g = g1
	print(1)
	print(' '.join(map(lambda x: str(x + 1), g[:(k + 1) // 2])))
main()


import sys
input = sys.stdin.readline
from math import sqrt
(n, m) = map(int, input().split())
k = int(-(-sqrt(n) // 1))
E = [[] for i in range(n + 1)]
D = [0] * (n + 1)
for i in range(m):
	(x, y) = map(int, input().split())
	E[x].append(y)
	E[y].append(x)
	D[x] += 1
	D[y] += 1
Q = [(d, i + 1) for (i, d) in enumerate(D[1:])]
import heapq
heapq.heapify(Q)
ANS = []
USE = [0] * (n + 1)
while Q:
	(d, i) = heapq.heappop(Q)
	if D[i] != d or USE[i] == 1:
		continue
	elif d >= k - 1:
		break
	else:
		ANS.append(i)
		USE[i] = 1
		for to in E[i]:
			if USE[to] == 0:
				USE[to] = 1
				for to2 in E[to]:
					if USE[to2] == 0:
						D[to2] -= 1
						heapq.heappush(Q, (D[to2], to2))
if len(ANS) >= k:
	print(1)
	print(*ANS[:k])
	sys.exit()
for i in range(1, n + 1):
	if USE[i] == 0:
		start = i
		break
Q = [start]
ANS = []
while Q:
	x = Q.pop()
	USE[x] = 1
	ANS.append(x)
	for to in E[x]:
		if USE[to] == 1:
			continue
		else:
			USE[to] = 1
			Q.append(to)
			break
for i in range(len(ANS)):
	if ANS[-1] in E[ANS[i]]:
		break
ANS = ANS[i:]
print(2)
print(len(ANS))
print(*ANS)


import sys
from math import *
from collections import defaultdict
from queue import deque
from heapq import heappush, heappop
lines = [line.strip() for line in sys.stdin.readlines()]
(n, m) = list(map(int, lines[0].split()))
edges = [set() for i in range(n)]
for i in range(1, m + 1):
	(u, v) = list(map(int, lines[i].split()))
	u -= 1
	v -= 1
	edges[u].add(v)
	edges[v].add(u)
nn = int(ceil(sqrt(n)))

def find_cycle(v, forbidden):
	used = set([v])
	forbidden = set(forbidden)
	ret = [v]
	while True:
		v = ret[-1]
		ss = edges[v] - used - forbidden
		nxt = None
		for s in ss:
			nxt = s
			break
		if nxt is None:
			break
		ret += [nxt]
		used.add(nxt)
	i = 0
	while ret[i] not in edges[ret[-1]]:
		i += 1
	return ret[i:]
q = []
for v in range(n):
	heappush(q, (len(edges[v]), v))
ind = set()
covered = set()
while q:
	(d, v) = heappop(q)
	if v in covered:
		continue
	ind.add(v)
	ss = set(edges[v])
	ss.add(v)
	if len(ind) == nn:
		print(1)
		print(' '.join(('%s' % (i + 1) for i in ind)))
		break
	if d >= nn - 1:
		ys = find_cycle(v, list(covered))
		print(2)
		print(len(ys))
		print(' '.join(('%s' % (i + 1) for i in ys)))
		break
	covered |= ss
	ws = set()
	for u in edges[v]:
		for w in edges[u]:
			ws.add(w)
	ws -= ss
	for w in ws:
		edges[w] -= ss
		heappush(q, (len(edges[w]), w))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
data = [map(int, line.split()) for line in sys.stdin.readlines()]
(n, m, k) = data[0]
dic = [[] for _ in range(n + 1)]
for i in range(1, m + 1):
	(u, v) = data[i]
	dic[u].append(v)
	dic[v].append(u)
now = [1]
father = [-1] * (n + 1)
p = [0] * (n + 1)
iscycle = False
while now:
	node = now.pop()
	for child in dic[node]:
		if child != father[node]:
			if father[child] != -1:
				iscycle = True
				odd = [child, node]
				break
			father[child] = node
			p[child] = p[node] + 1
			now.append(child)
	if iscycle:
		break
if iscycle:
	(a, b) = (odd[0], odd[1])
	(x, y) = ([], [])
	node = a
	while node > 1:
		x.append(node)
		node = father[node]
	x.append(1)
	u = set(x)
	node = b
	while node > 1:
		y.append(node)
		node = father[node]
		if node in u:
			t = p[a] - p[node] + 1
			x = x[:t]
			break
	x += y[::-1]
	if len(x) <= k:
		print(2)
		print(len(x))
		print_list(x)
	else:
		print(1)
		print_list(x[:k:2])
else:
	print(1)
	s0 = [i for i in range(1, n + 1) if p[i] & 1 == 0]
	s1 = [i for i in range(1, n + 1) if p[i] & 1 == 1]
	if len(s0) > len(s1):
		print_list(s0[:k + 1 >> 1])
	else:
		print_list(s1[:k + 1 >> 1])


from collections import defaultdict
(n, m, k) = list(map(int, input().split()))
desreslen = k // 2 + k % 2
links = defaultdict(set)
for v in range(m):
	(a, b) = list(map(int, input().split()))
	links[a].add(b)
	links[b].add(a)
label = defaultdict(int)
prev = defaultdict(int)
start = 0
stk = [1]
label[stk[start]] = 1
cycled = False
while start < len(stk):
	cur = stk[start]
	for v in links[cur]:
		if prev[cur] == v:
			continue
		if label[v] == 0:
			stk.append(v)
			label[v] = label[cur] + 1
			prev[v] = cur
		else:
			cycled = (cur, v)
			break
	if cycled:
		break
	start += 1
if cycled:
	(a, b) = cycled
	acycle = [a]
	bcycle = [b]
	if label[acycle[-1]] > label[bcycle[-1]]:
		acycle.append(prev[acycle[-1]])
	elif label[acycle[-1]] < label[bcycle[-1]]:
		bcycle.append(prev[bcycle[-1]])
	while acycle[-1] != bcycle[-1]:
		acycle.append(prev[acycle[-1]])
		bcycle.append(prev[bcycle[-1]])
	cycle = acycle[:-1] + bcycle[::-1]
	if len(cycle) <= k:
		print(2)
		print(len(cycle))
		print(*cycle)
	else:
		print(1)
		print(*cycle[:2 * desreslen:2])
else:
	evens = [v for v in label if label[v] % 2]
	oddss = [v for v in label if label[v] % 2 == 0]
	if len(oddss) > len(evens):
		res = oddss
	else:
		res = evens
	print(1)
	print(*list(res)[:desreslen])


from math import ceil
import sys
input = sys.stdin.buffer.readline

def dfs(graph, n):
	depth = [0 for i in range(n + 1)]
	parent = [0 for i in range(n + 1)]
	mk = [0 for i in range(n + 1)]
	q = []
	q.append(1)
	q2 = []
	while q:
		node = q.pop()
		if depth[node]:
			continue
		q2.append(node)
		depth[node] = depth[parent[node]] + 1
		for no in graph[node]:
			if depth[no]:
				if 2 < depth[node] - depth[no] + 1 <= k:
					ans = []
					u = node
					while node != parent[no]:
						ans.append(node)
						node = parent[node]
					return (False, ans)
			else:
				parent[no] = node
				q.append(no)
	ans = []
	while q2:
		u = q2.pop()
		if not mk[u]:
			ans.append(u)
			for v in graph[u]:
				mk[v] = 1
	return (True, ans[:ceil(k / 2)])
(n, m, k) = [int(c) for c in input().split()]
graph = {i: [] for i in range(1, n + 1)}
for i in range(m):
	(u, v) = [int(c) for c in input().split()]
	graph[u].append(v)
	graph[v].append(u)
(a, b) = dfs(graph, n)
if a:
	print(1)
	print(*b)
else:
	print(2)
	print(len(b))
	print(*b)


from collections import deque
from math import ceil
import sys
sys.setrecursionlimit(10 ** 8)
back_edge = []
visited = []
parent = []
level = []

def dfs(nod):
	stack = [nod]
	while stack:
		node = stack.pop()
		visited[node] = True
		if len(back_edge) != 0:
			return
		visited[node] = True
		takenodes = []
		for i in adj[node]:
			if visited[i] and parent[node] != i:
				takenodes.append(i)
		if len(takenodes) != 0:
			maximum_depth = -1
			max_node = -1
			for i in takenodes:
				if level[i] > maximum_depth:
					maximum_depth = level[i]
					max_node = i
			back_edge.append((node, max_node))
			return
		for i in adj[node]:
			if not visited[i]:
				parent[i] = node
				level[i] = level[node] + 1
				stack.append(i)
(n, m, k) = map(int, input().split(' '))
adj = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split(' '))
	adj[a].append(b)
	adj[b].append(a)
if m == n - 1:
	q = deque()
	q.append(1)
	sign = [0] * (n + 1)
	visited = [False] * (n + 1)
	sign[1] = 0
	done = 0
	while done < n:
		curr = q.popleft()
		visited[curr] = True
		for i in adj[curr]:
			if not visited[i]:
				q.append(i)
				sign[i] = 1 - sign[curr]
		done += 1
	l1 = []
	l0 = []
	for i in range(1, n + 1):
		if sign[i] == 1:
			l0.append(i)
		else:
			l1.append(i)
	print(1)
	if len(l0) > len(l1):
		print(*l0[:ceil(k / 2)])
	else:
		print(*l1[:ceil(k / 2)])
else:
	parent = [0] * (n + 1)
	visited = [False] * (n + 1)
	level = [0] * (n + 1)
	level[1] = 0
	try:
		dfs(1)
	except Exception as e:
		print(e)
	curr = back_edge[0][0]
	path = []
	while curr != back_edge[0][1]:
		path.append(curr)
		curr = parent[curr]
	path.append(back_edge[0][1])
	if len(path) <= k:
		print(2)
		print(len(path))
		print(*path)
	else:
		print(1)
		doned = 0
		for i in range(0, len(path), 2):
			if doned == ceil(k / 2):
				break
			doned += 1
			print(path[i], end=' ')
		print()


class LowestCommonAncestor:

	def __init__(self, tree, root):
		self.n = len(tree)
		self.depth = [0] * self.n
		self.log_size = self.n.bit_length()
		self.parent = [[-1] * self.n for i in range(self.log_size)]
		q = [(root, -1)]
		while q:
			(v, par) = q.pop()
			for chi_v in tree[v]:
				if chi_v == par:
					continue
				self.parent[0][chi_v] = v
				self.depth[chi_v] = self.depth[v] + 1
				q.append((chi_v, v))
		for k in range(self.log_size - 1):
			for v in range(self.n):
				if self.parent[k][v] == -1:
					self.parent[k + 1][v] = -1
				else:
					self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]

	def lca(self, u, v):
		if self.depth[u] > self.depth[v]:
			(u, v) = (v, u)
		for k in range(self.log_size):
			if self.depth[v] - self.depth[u] >> k & 1:
				v = self.parent[k][v]
		if u == v:
			return u
		for k in reversed(range(self.log_size)):
			if self.parent[k][u] != self.parent[k][v]:
				u = self.parent[k][u]
				v = self.parent[k][v]
		return self.parent[0][u]
from collections import deque
import sys
input = sys.stdin.buffer.readline
(n, m, k) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
OFFSET = 10 ** 6
graph = [[] for i in range(n)]
for (a, b) in info:
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
tree = [[] for i in range(n)]
edges = set([])
used = [False] * n
out_degree = [len(graph[i]) for i in range(n)]

def dfs_tree(self, root):
	st = [-1, root, 0]
	while st:
		(prv_v, v, ind) = (st[-3], st[-2], st[-1])
		if not ind and used[v]:
			st.pop()
			st.pop()
			st.pop()
		else:
			used[v] = True
			if ind < out_degree[v]:
				st[-1] += 1
				st.append(v)
				st.append(graph[v][ind])
				st.append(0)
			else:
				st.pop()
				st.pop()
				st.pop()
				if prv_v != -1:
					edges.add(min(prv_v, v) * OFFSET + max(prv_v, v))
					tree[v].append(prv_v)
					tree[prv_v].append(v)
dfs_tree(graph, 0)
lca = LowestCommonAncestor(tree, 0)
for (a, b) in info:
	a -= 1
	b -= 1
	if min(a, b) * OFFSET + max(a, b) in edges:
		continue
	dist = abs(lca.depth[a] - lca.depth[b]) + 1
	if dist <= k:
		if lca.depth[a] < lca.depth[b]:
			(a, b) = (b, a)
		ans = [a + 1]
		while a != b:
			a = lca.parent[0][a]
			ans.append(a + 1)
		print(2)
		print(len(ans))
		print(*ans)
		exit()
stack = [i for i in range(n) if len(tree[i]) == 1]
visited = [False] * n
q = deque([])
for i in stack:
	visited[i] = True
	q.append(i)
col = [False] * n
while q:
	v = q.popleft()
	flag = True
	for nxt_v in graph[v]:
		flag &= not col[nxt_v]
		if visited[nxt_v]:
			continue
		visited[nxt_v] = True
		q.append(nxt_v)
	if flag:
		col[v] = True
ans = []
for i in range(n):
	if col[i] == True and len(ans) < (k + 1) // 2:
		ans.append(i + 1)
if len(ans) == (k + 1) // 2:
	print(1)
	print(*ans)


from collections import deque
from sys import stdin
import sys
from math import ceil
sys.setrecursionlimit(3 * 10 ** 5)
(n, m) = map(int, stdin.readline().split())
rn = ceil(n ** 0.5)
lis = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, stdin.readline().split())
	u -= 1
	v -= 1
	lis[u].append(v)
	lis[v].append(u)
stk = [0]
slis = [0] * n
d = [float('inf')] * n
p = [i for i in range(n)]
d[0] = 0
while stk:
	v = stk[-1]
	if slis[v] < len(lis[v]):
		nex = lis[v][slis[v]]
		slis[v] += 1
		if d[nex] == float('inf'):
			d[nex] = d[v] + 1
			p[nex] = v
			stk.append(nex)
		elif d[v] - d[nex] + 1 >= rn:
			back = [v + 1]
			now = v
			while now != nex:
				now = p[now]
				back.append(now + 1)
			print(2)
			print(len(back))
			print(*back)
			sys.exit()
	else:
		del stk[-1]
dlis = [[] for i in range(rn - 1)]
for i in range(n):
	dlis[d[i] % (rn - 1)].append(i + 1)
maxind = 0
for i in range(rn - 1):
	if len(dlis[i]) > len(dlis[maxind]):
		maxind = i
print(1)
print(*dlis[maxind][:rn])


import os
import sys
from io import BytesIO, IOBase
import threading
from math import floor
from collections import deque
from math import gcd
mod = 998244353

def main():
	(n, m, k) = map(int, input().split())
	graph = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		graph[u].append(v)
		graph[v].append(u)
	color = [-1] * n
	parent = [-1] * n
	color[0] = 0
	bfs = deque([0])
	painted = [0] * n
	p = 0
	while len(bfs):
		node = bfs.popleft()
		col = 0 if color[node] else 1
		for adj in graph[node]:
			if color[adj] == -1:
				parent[adj] = node
				color[adj] = col
				bfs.append(adj)
			elif color[adj] != col:
				p = node
				st = []
				while p != -1:
					st.append(p + 1)
					p = parent[p]
				p = adj
				st1 = []
				while p != -1:
					st1.append(p + 1)
					p = parent[p]
				prev = st[-1]
				while len(st1) > 0 and len(st) > 0 and (st1[-1] == st[-1]):
					prev = st[-1]
					st1.pop()
					st.pop()
				l = len(st1) + len(st) + 1
				ans = st1 + [prev] + st[::-1]
				if l > k:
					print('1')
					print(*[j for (i, j) in enumerate(ans) if i % 2 == 1])
					return
				print('2')
				print(l)
				print(*ans)
				return
		painted[node] = 1
		p += 1
		if p >= k:
			print('1')
			for i in range(n):
				if not painted[i]:
					color[i] = -1
			cn1 = color.count(1)
			cn2 = color.count(0)
			c = 1 if cn1 > cn2 else 0
			ans = [i + 1 for i in range(n) if color[i] == c]
			print(*ans[:(k + 1) // 2])
			return
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def calc_group_num(self):
		N = len(self._parent)
		ans = 0
		for i in range(N):
			if self.find_root(i) == i:
				ans += 1
		return ans

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

	def back(self, s, t):
		data = self.shortest_path(s)
		val = data[t]
		path = [t]
		pos = t
		while pos != s:
			for e in self.G[pos]:
				pv = e.to
				if data[pv] == data[pos] - 1:
					pos = pv
					break
			path.append(pos)
		return path
import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
uf = UnionFindVerSize(n)
di = Dijkstra(n)
edge = [[] for i in range(n)]
flag = True
path = []
if m > n - 1:
	for i in range(m):
		(u, v) = map(int, input().split())
		if uf.is_same_group(u - 1, v - 1) and flag:
			start = u - 1
			end = v - 1
			flag = False
		else:
			uf.unite(u - 1, v - 1)
			di.add(u - 1, v - 1, 1)
			di.add(v - 1, u - 1, 1)
	path = di.back(end, start)
	path = [path[i] + 1 for i in range(len(path))]
	N = len(path)
	if k >= N:
		print(2)
		print(N)
		print(*path)
	else:
		print(1)
		ans = [path[2 * i] for i in range((k + 1) // 2)]
		print(*ans)
else:
	from collections import deque
	for i in range(m):
		(u, v) = map(int, input().split())
		edge[u - 1].append(v - 1)
		edge[v - 1].append(u - 1)
	color = [-1] * n
	color[0] = 0
	que = deque([0])
	while que:
		v = que.popleft()
		for nv in edge[v]:
			if color[nv] == -1:
				color[nv] = (1 + color[v]) % 2
				que.append(nv)
	A = color.count(1)
	B = color.count(0)
	print(1)
	if A >= (k + 1) // 2:
		ans = [i + 1 for i in range(n) if color[i] == 1]
		ans = ans[:(k + 1) // 2]
		print(*ans)
	else:
		ans = [i + 1 for i in range(n) if color[i] == 0]
		ans = ans[:(k + 1) // 2]
		print(*ans)


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
E = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	E[x].append(y)
	E[y].append(x)
Q = [(0, 1)]
DEPTH = [0] * (n + 1)
FROM = [0] * (n + 1)
cy_start = -1
while Q:
	(fr, x) = Q.pop()
	DEPTH[x] = DEPTH[fr] + 1
	FROM[x] = fr
	for to in E[x]:
		if DEPTH[to] == 0:
			Q.append((x, to))
		elif to != FROM[x]:
			cy_start = x
			break
	if cy_start != -1:
		CYCLE = [cy_start]
		MAXDEPTH = -1
		for to in E[cy_start]:
			if to == FROM[cy_start]:
				continue
			if DEPTH[to] > MAXDEPTH:
				MAXDEPTH = DEPTH[to]
				cy_goal = to
		CYCLE = [cy_start]
		while cy_start != cy_goal:
			cy_start = FROM[cy_start]
			CYCLE.append(cy_start)
		break
if cy_start == -1:
	Q = [1]
	COLOR = [-1] * (n + 1)
	COLOR[1] = 0
	while Q:
		x = Q.pop()
		for to in E[x]:
			if COLOR[to] == -1:
				COLOR[to] = 1 - COLOR[x]
				Q.append(to)
	ANS = []
	for i in range(1, n + 1):
		if COLOR[i] == 0:
			ANS.append(i)
	if len(ANS) >= (k + 1) // 2:
		print(1)
		print(*ANS[:(k + 1) // 2])
	else:
		ANS = set(range(1, n + 1)) - set(ANS)
		print(1)
		print(*list(ANS)[:(k + 1) // 2])
elif len(CYCLE) <= k:
	print(2)
	print(len(CYCLE))
	print(*CYCLE)
else:
	print(1)
	ANS = []
	for i in range(0, len(CYCLE), 2):
		ANS.append(CYCLE[i])
	print(*ANS[:(k + 1) // 2])


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
from collections import deque

def k_independent_set(n, k):
	color = [-1] * n
	q = deque()
	q.append((0, 0))
	color[0] = 0
	while q:
		(v, c) = q.popleft()
		for w in g[v]:
			if color[w] == -1:
				color[w] = 1 - c
				q.append((w, 1 - c))
	c0 = [i + 1 for i in range(n) if color[i] == 0]
	c1 = [i + 1 for i in range(n) if color[i] == 1]
	if len(c0) >= (k + 1) // 2:
		return (1, c0[:(k + 1) // 2])
	else:
		return (1, c1[:(k + 1) // 2])

def find_cycle(n):
	prev = [-1] * n
	t = [-1] * n
	q = deque()
	q.append(0)
	t[0] = 0
	while q:
		v = q.popleft()
		for w in g[v]:
			if t[w] != -1:
				if t[w] >= t[v]:
					s = w
					e = v
					p1 = [s]
					p2 = [e]
					while s != e:
						if t[s] >= t[e]:
							s = prev[s]
							p1.append(s)
						else:
							e = prev[e]
							p2.append(e)
					p1.pop()
					return p1 + list(reversed(p2))
			else:
				t[w] = t[v] + 1
				prev[w] = v
				q.append(w)

def k_cycle(n, k):
	c = find_cycle(n)
	cn = len(c)
	cg = {}
	for i in range(cn):
		cg[c[i]] = [c[(i - 1 + cn) % cn], c[(i + 1) % cn]]
	while len(c) > k:
		found = False
		for i in range(cn):
			cv = c[i]
			cutting_edges = [w for w in g[cv] if w in cg and w != cg[cv][0] and (w != cg[cv][1])]
			if len(cutting_edges) == 0:
				continue
			w = cutting_edges[0]
			new_c = []
			for j in range(i, i + cn):
				new_c.append(c[j % cn])
				if c[j % cn] == w:
					break
			c = new_c
			found = True
			break
		if not found:
			break
	if len(c) <= k:
		return (2, [i + 1 for i in c])
	res = [ci + 1 for (i, ci) in enumerate(c) if i % 2 == 0]
	return (1, res[:min((k + 1) // 2, len(res))])

def solve(n, m, k):
	is_tree = m == n - 1
	if is_tree:
		return k_independent_set(n, k)
	else:
		return k_cycle(n, k)
g = []

def main():
	global g
	(n, m, k) = ria()
	g = [[] for _ in range(n)]
	for _ in range(m):
		(v, w) = ria()
		g[v - 1].append(w - 1)
		g[w - 1].append(v - 1)
	(t, res) = solve(n, m, k)
	wi(t)
	if t == 2:
		wi(len(res))
	wia(res)

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def dfs(graph, alpha):
	n = len(graph)
	visited = [False] * n
	parents = [-1] * n
	colors = [1] * n
	stack = [alpha]
	cycle = []
	while stack:
		v = stack[-1]
		if not visited[v]:
			visited[v] = True
			for u in graph[v]:
				if not visited[u]:
					stack.append(u)
					colors[u] = 1 - colors[v]
					if parents[u] == -1:
						parents[u] = v
				elif u != parents[v]:
					cycle = [u, v]
		else:
			stack.pop()
	return (colors, parents, cycle)
for _ in range(int(input()) if not True else 1):
	(n, m, k) = map(int, input().split())
	graph = [[] for __ in range(n + 1)]
	edges = set()
	for i in range(m):
		(x, y) = map(int, input().split())
		graph[x] += [y]
		graph[y] += [x]
		edges.add((x, y))
		edges.add((y, x))
	if m == n - 1:
		print(1)
		(colors, parents, cycle) = dfs(graph, 1)
		(zero, one) = ([], [])
		for i in range(1, n + 1):
			if colors[i]:
				one += [i]
			else:
				zero += [i]
			if max(len(one), len(zero)) == ceil(k / 2):
				break
		if len(one) == ceil(k / 2):
			print(*one)
		else:
			print(*zero)
		continue
	(colors, parents, cycle) = dfs(graph, 1)

	def shortest_path(graph, alpha, omega, parents):
		path = [omega]
		v = omega
		while parents[v] != -1:
			path += [parents[v]]
			v = parents[v]
		return path[::-1]
	c = shortest_path(graph, cycle[0], cycle[1], parents) + shortest_path(graph, cycle[1], cycle[0], parents)[::-1]
	from collections import deque
	c = deque(c)
	while len(c) >= 4 and c[1] == c[-2]:
		c.popleft()
		c.pop()
	e2 = set()
	vtc = set()
	for i in range(1, len(c)):
		e2.add((c[i - 1], c[i]))
		vtc.add(c[i])
	rdex = {}
	for i in range(len(c)):
		rdex[c[i]] = i
	(mr1, mr2) = (69696969, 69696969)
	for edge in edges:
		if edge in e2 or (edge[1], edge[0]) in e2:
			continue
		if edge[0] in vtc and edge[1] in vtc:
			(r1, r2) = (rdex[edge[0]], rdex[edge[1]])
			(r1, r2) = (min(r1, r2), max(r1, r2))
			if r1 < mr1:
				mr1 = r1
				mr2 = r2
	c = list(c)
	c = c[:mr1 + 1] + c[mr2:]
	c = c[:-1]
	if len(c) <= k:
		print(2)
		print(len(c))
		print(*c)
	else:
		print(1)
		print(*[c[i] for i in range(0, len(c), 2)][:ceil(k / 2)])


import sys
import math
from collections import defaultdict
from collections import deque
(N, M, K) = [int(_) for _ in sys.stdin.readline().split()]
edges = [set() for i in range(N)]
for i in range(M):
	(u, v) = [int(_) for _ in sys.stdin.readline().split()]
	edges[u - 1].add(v - 1)
	edges[v - 1].add(u - 1)

def bfs_cycle(edges, node):
	visited = [False] * N
	Q = deque()
	Q.append(node)
	parent = {}
	parent[node] = None
	while Q:
		el = Q.popleft()
		visited[el] = True
		for neighbour in edges[el]:
			if visited[neighbour]:
				if parent[el] != neighbour:
					p1 = neighbour
					p2 = el
					p = {}
					p[p1] = (0, None)
					p[p2] = (0, None)
					for i in range(K):
						pp1 = parent[p1]
						if pp1 is not None:
							if pp1 in p:
								answer1 = []
								sp = p1
								while sp is not None:
									answer1.append(sp)
									sp = p[sp][1]
								answer2 = []
								sp = pp1
								while sp is not None:
									answer2.append(sp)
									sp = p[sp][1]
								return answer1 + answer2[::-1]
							p[pp1] = (p[p1][0] + 1, p1)
							p1 = pp1
						pp2 = parent[p2]
						if pp2 is not None:
							if pp2 in p:
								answer1 = []
								sp = p2
								while sp is not None:
									answer1.append(sp)
									sp = p[sp][1]
								answer2 = []
								sp = pp2
								while sp is not None:
									answer2.append(sp)
									sp = p[sp][1]
								return answer1 + answer2[::-1]
							p[pp2] = (p[p2][0] + 1, p2)
							p2 = pp2
				continue
			visited[neighbour] = True
			parent[neighbour] = el
			Q.append(neighbour)
	return None

def bfs_set(edges, node):
	visited = [False] * N
	Q = deque()
	Q.append(node)
	D = [-1] * N
	D[node] = 0
	parent = {}
	parent[node] = None
	answerP = [node]
	if len(answerP) >= math.ceil(K / 2):
		return answerP
	answerI = []
	while Q:
		el = Q.popleft()
		visited[el] = True
		for neighbour in edges[el]:
			if visited[neighbour]:
				continue
			visited[neighbour] = True
			D[neighbour] = D[el] + 1
			parent[neighbour] = el
			if D[neighbour] % 2:
				answerI.append(neighbour)
			else:
				answerP.append(neighbour)
			if len(answerI) >= math.ceil(K / 2):
				return answerI
			if len(answerP) >= math.ceil(K / 2):
				return answerP
			Q.append(neighbour)
	assert False
cycle = bfs_cycle(edges, 0)
if cycle:
	if len(cycle) <= K:
		print(2)
		print(len(cycle))
		print(' '.join([str(i + 1) for i in cycle]))
	else:
		print(1)
		answer = []
		for i in range(math.ceil(K / 2)):
			answer.append(cycle[2 * i])
		print(' '.join([str(i + 1) for i in answer]))
else:
	answer = bfs_set(edges, 0)
	print(1)
	print(' '.join([str(i + 1) for i in answer]))


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m, k) = map(int, input().split())
connectionList = []
treeConnectionList = []
isCovered = []
isAddedInQueue = []
distance = []
queue = []
queueIndex = -1
for _ in range(n):
	connectionList.append([])
	treeConnectionList.append([])
	isCovered.append(False)
	isAddedInQueue.append(False)
	distance.append(-1)
for _ in range(m):
	(a, b) = map(int, input().split())
	connectionList[a - 1].append(b - 1)
	connectionList[b - 1].append(a - 1)
queue.append((0, -1, 0))
queueIndex = 0
distance[0] = 0
isCovered[0] = True
isAddedInQueue[0] = True
isThereCycle = False
treeCounter = 0
while True:
	if queueIndex >= len(queue):
		break
	cur = queue[queueIndex]
	queueIndex += 1
	isCovered[cur[0]] = True
	distance[cur[0]] = cur[2]
	if cur[1] != -1:
		treeConnectionList[cur[0]].append(cur[1])
		treeConnectionList[cur[1]].append(cur[0])
	for vertex in connectionList[cur[0]]:
		if isCovered[vertex] and cur[1] != vertex:
			isThereCycle = True
			cycleVertex = (cur[0], vertex)
			break
		if not isAddedInQueue[vertex]:
			queue.append((vertex, cur[0], cur[2] + 1))
			isAddedInQueue[vertex] = True
	if isThereCycle:
		break
	treeCounter += 1
	if treeCounter >= k:
		break
if isThereCycle:
	queueCycle = []
	isAddedInQueueCycle = []
	pathMother = []
	for _ in range(n):
		isAddedInQueueCycle.append(False)
		pathMother.append(-1)
	queueCycle.append((cycleVertex[0], -1))
	isAddedInQueueCycle[cycleVertex[0]] = True
	queueCycleIndex = 0
	while True:
		if queueCycleIndex >= len(queueCycle):
			break
		cur = queueCycle[queueCycleIndex]
		queueCycleIndex += 1
		pathMother[cur[0]] = cur[1]
		if cur[0] == cycleVertex[1]:
			break
		for vertex in treeConnectionList[cur[0]]:
			if not isAddedInQueueCycle[vertex]:
				queueCycle.append((vertex, cur[0]))
				isAddedInQueueCycle[vertex] = True
	cycle = [cycleVertex[1]]
	index = 0
	while True:
		if pathMother[cycle[index]] == -1:
			break
		else:
			cycle.append(pathMother[cycle[index]])
			index = index + 1
	res = []
	for i in cycle:
		res.append(str(i + 1))
	print('2')
	print(len(cycle))
	print(' '.join(res))
else:
	indepSet1 = []
	indepSet2 = []
	for i in range(n):
		if distance[i] == -1:
			continue
		elif distance[i] % 2 == 1:
			indepSet1.append(i)
		else:
			indepSet2.append(i)
	answer = indepSet1 if len(indepSet1) > len(indepSet2) else indepSet2
	res = []
	for i in answer[0:k - k // 2]:
		res.append(str(i + 1))
	print('1')
	print(' '.join(res))


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

def bfs(g, s):
	q = deque([s])
	d = {s: 0}
	while q:
		v = q.popleft()
		for to in g[v]:
			if to not in d:
				q.append(to)
				d[to] = d[v] + 1
	return d

def findCycle(s, getNbr):
	q = deque([s])
	dist = {s: 0}
	par = {s: None}
	while q:
		v = q.popleft()
		d = dist[v]
		for to in getNbr(v):
			if to not in dist:
				q.append(to)
				dist[to] = d + 1
				par[to] = v
			else:
				if dist[to] == d - 1:
					assert to == par[v]
					continue
				assert dist[to] in [d, d + 1]
				path1 = [to]
				path2 = [v]
				while path1[-1] != path2[-1]:
					if dist[path1[-1]] >= dist[path2[-1]]:
						path1.append(par[path1[-1]])
					else:
						path2.append(par[path2[-1]])
				assert path1[-1] == path2[-1]
				path2.pop()
				return path1 + path2[::-1]
	return None
(n, m, k) = map(int, input().split())
g = [[] for i in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)

def get_nbr(u):
	return g[u]
cycle = findCycle(0, get_nbr)
if cycle:
	if len(cycle) <= k:
		for i in range(len(cycle)):
			cycle[i] += 1
		print(2)
		print(len(cycle))
		print(*cycle)
	else:
		ans = []
		for i in range((k + 1) // 2):
			ans.append(cycle[i * 2] + 1)
		print(1)
		print(*ans)
else:
	dist = bfs(g, 0)
	(odd, even) = ([], [])
	for (v, d) in dist.items():
		if d % 2 == 0:
			odd.append(v + 1)
		else:
			even.append(v + 1)
	if len(even) >= (k + 1) // 2:
		print(1)
		print(*even[:(k + 1) // 2])
	else:
		print(1)
		print(*odd[:(k + 1) // 2])