It's the year 5555. You have a graph, and you want to find a long cycle and a huge independent set, just because you can. But for now, let's just stick with finding either.

Given a connected graph with $n$ vertices, you can choose to either:

  find an independent set that has exactly $\lceil\sqrt{n}\rceil$ vertices.

 find a simple cycle of length at least $\lceil\sqrt{n}\rceil$. 

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 you can always solve one of these problems, but it's too long to fit this margin.


-----Input-----

The first line contains two integers $n$ and $m$ ($5 \le n \le 10^5$, $n-1 \le m \le 2 \cdot 10^5$) — the number of vertices and edges in the graph.

Each of the next $m$ lines contains two space-separated 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\sqrt{n}\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 integers not exceeding $n$, the vertices in the desired cycle, in the order they appear in the cycle.


-----Examples-----
Input
6 6
1 3
3 4
4 2
2 6
5 6
5 1

Output
1
1 6 4
Input
6 8
1 3
3 4
4 2
2 6
5 6
5 1
1 4
2 5

Output
2
4
1 5 2 4
Input
5 4
1 2
1 3
2 4
2 5

Output
1
3 4 5 


-----Note-----

In the first sample:

[Image]

Notice that you can solve either problem, so printing the cycle $2-4-3-1-5-6$ is also acceptable.

In the second sample:

[Image]

Notice that if there are multiple answers you can print any, so printing the cycle $2-5-6$, for example, is acceptable.

In the third sample:

$A$

Source: codeforces | Difficulty: MEDIUM


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


import sys
input = sys.stdin.readline
(n, m) = list(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 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[:req], None)
(iset, cyc) = dfs()
if iset:
	print(1)
	print(*iset)
else:
	print(2)
	print(len(cyc))
	print(*cyc)


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


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