You've got a undirected graph G, consisting of n nodes. We will consider the nodes of the graph indexed by integers from 1 to n. We know that each node of graph G is connected by edges with at least k other nodes of this graph. Your task is to find in the given graph a simple cycle of length of at least k + 1.

A simple cycle of length d (d > 1) in graph G is a sequence of distinct graph nodes v_1, v_2, ..., v_{d} such, that nodes v_1 and v_{d} are connected by an edge of the graph, also for any integer i (1 ≤ i < d) nodes v_{i} and v_{i} + 1 are connected by an edge of the graph.


-----Input-----

The first line contains three integers n, m, k (3 ≤ n, m ≤ 10^5; 2 ≤ k ≤ n - 1) — the number of the nodes of the graph, the number of the graph's edges and the lower limit on the degree of the graph node. Next m lines contain pairs of integers. The i-th line contains integers a_{i}, b_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}) — the indexes of the graph nodes that are connected by the i-th edge. 

It is guaranteed that the given graph doesn't contain any multiple edges or self-loops. It is guaranteed that each node of the graph is connected by the edges with at least k other nodes of the graph.


-----Output-----

In the first line print integer r (r ≥ k + 1) — the length of the found cycle. In the next line print r distinct integers v_1, v_2, ..., v_{r} (1 ≤ v_{i} ≤ n) — the found simple cycle.

It is guaranteed that the answer exists. If there are multiple correct answers, you are allowed to print any of them.


-----Examples-----
Input
3 3 2
1 2
2 3
3 1

Output
3
1 2 3 
Input
4 6 3
4 3
1 2
1 3
1 4
2 3
2 4

Output
4
3 4 1 2

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Starter code:

Solutions:
(n, m, k) = [int(x) for x in input().split()]
adj = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v) = [int(x) for x in input().split()]
	adj[u].append(v)
	adj[v].append(u)
mark = [False for _ in range(n + 1)]
c = [1]
while True:
	mark[c[-1]] = True
	for v in adj[c[-1]]:
		if not mark[v]:
			c.append(v)
			break
	else:
		mark = [False for _ in range(n + 1)]
		for v in adj[c[-1]]:
			mark[v] = True
		for i in range(len(c)):
			if mark[c[i]]:
				start = i
				break
		print(len(c) - start)
		print(' '.join(map(str, c[start:])))
		break


f = 200001
v = [0] * f
g = [[] for _ in [0] * f]
s = [1]
(n, m, k) = map(int, input().split())
for _ in range(m):
	(a, b) = map(int, input().split())
	g[b] += (a,)
	g[a] += (b,)
while 1:
	v[s[-1]] = 1
	for i in g[s[-1]]:
		if v[i] < 1:
			s += (i,)
			break
	else:
		t = set(g[s[-1]])
		for i in range(len(s)):
			if s[i] in t:
				exit(print(len(s) - i, *s[i:]))


(n, m, k) = [int(x) for x in input().split()]
adj = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = [int(x) for x in input().split()]
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
mark = [False for _ in range(n)]
c = [0]
mark[0] = True
while True:
	augmented = False
	for v in adj[c[-1]]:
		if not mark[v]:
			c.append(v)
			augmented = mark[v] = True
			break
	if not augmented:
		break
mark = [False for _ in range(n)]
for v in adj[c[-1]]:
	mark[v] = True
start = 0
for i in range(len(c)):
	if mark[c[i]]:
		start = i
		break
print(len(c) - start)
for i in range(start, len(c)):
	print(c[i] + 1, end=' ')


def find_cycle_optimum(n, m, k, adj):
	path = [1]
	visited = [-1 for _ in range(n + 1)]
	visited[1] = 1
	while True:
		v = path[-1]
		visited[v] = len(path) - 1
		for w in adj[v]:
			if visited[w] == -1:
				path.append(w)
				break
			elif len(path) - visited[w] > k:
				return path[visited[w]:]

def main():
	(n, m, k) = [int(i) for i in input().split()]
	adj = [[] for i in range(n + 1)]
	for _ in range(m):
		(u, v) = [int(i) for i in input().split()]
		adj[u].append(v)
		adj[v].append(u)
	c = find_cycle_optimum(n, m, k, adj)
	l = len(c)
	print(l)
	print(' '.join((str(v) for v in c)))
main()


class Graph:

	def __init__(self, size=0):
		self.g = [[] for i in range(size)]
		self.size = size
		self.path = []

	def addEdge(self, u, v):
		try:
			self.g[u].append(v)
			self.g[v].append(u)
		except IndexError:
			pass

	def DFSAux(self, v, k, start, root):
		d = 0
		visit = [root]
		while len(visit) > 0:
			r = visit.pop()
			if v[r] == -1:
				v[r] = d
				d += 1
				self.path.append(r)
				for e in self.g[r]:
					if v[e] != -1:
						if v[r] - v[e] + 1 >= k:
							self.path = self.path[v[e]:v[r] + 1]
							return True
					else:
						visit.append(e)
		return False

	def findCycle(self, k):
		v = [-1 for i in range(self.size)]
		self.DFSAux(v, k, 0, 0)
values = list(map(int, input().split()))
g = Graph(values[0])
m = values[1]
while m > 0:
	m -= 1
	edges = list(map(int, input().split()))
	g.addEdge(edges[0] - 1, edges[1] - 1)
g.findCycle(values[2] + 1)
print(len(g.path))
for i in g.path:
	print(i + 1, end=' ')
print()


(n, m, k) = map(int, input().split())
d = {}
for _ in range(m):
	(u, v) = map(int, input().split())
	if u not in d:
		d[u] = [v]
	else:
		d[u].append(v)
	if v not in d:
		d[v] = [u]
	else:
		d[v].append(u)
stack = []
not_visited = set(range(1, n + 1))
while not_visited:
	if not stack:
		stack.append((not_visited.pop(), 1, 0))
		path = []
		visited = {}
		c = 0
	(p, l, parent) = stack.pop()
	path.append(p)
	visited[p] = c
	c += 1
	if p in not_visited:
		not_visited.remove(p)
	f = False
	for x in d[p]:
		if x not in visited:
			stack.append((x, l + 1, p))
		elif c - visited[x] > k:
			path = path[visited[x]:]
			f = True
			break
	if f:
		break
print(len(path))
print(*path)


def cycle(G, K):
	path = [1]
	pos = [-1 for i in range(len(G) + 1)]
	while True:
		v = path[-1]
		pos[v] = len(path) - 1
		for u in G[v]:
			if pos[u] == -1:
				path.append(u)
				break
			elif len(path) - pos[u] > K:
				return path[pos[u]:]

def main():
	(N, M, K) = [int(i) for i in input().split()]
	G = {i: set() for i in range(1, N + 1)}
	for m in range(M):
		(i, j) = [int(i) for i in input().split()]
		G[i].add(j)
		G[j].add(i)
	path = cycle(G, K)
	print(len(path))
	temp = ' '.join((str(v) for v in path))
	print(temp)
main()


from collections import defaultdict

class CycleInGraph:

	def __init__(self, n, m, k, edges):
		(self.n, self.m, self.k) = (n, m, k)
		self.edges = edges
		self.edge_map = defaultdict(list)
		for (x, y) in self.edges:
			self.edge_map[x - 1].append(y - 1)
			self.edge_map[y - 1].append(x - 1)

	def print_cycle(self):
		check = [0] * self.n
		nodes = [0]
		check[0] = 1
		loop_check = True
		while loop_check:
			loop_check = False
			for v in self.edge_map[nodes[-1]]:
				if check[v] == 0:
					loop_check = True
					check[v] = 1
					nodes.append(v)
					break
		nodes_map = {nodes[i]: i for i in range(len(nodes))}
		min_pos = min([nodes_map[v] for v in self.edge_map[nodes[-1]]])
		print(len(nodes) - min_pos)
		print(*list(map(lambda x: x + 1, nodes[min_pos:])))
(n, m, k) = list(map(int, input().strip(' ').split(' ')))
edges = []
for i in range(m):
	(x, y) = list(map(int, input().strip(' ').split(' ')))
	edges.append((x, y))
cg = CycleInGraph(n, m, k, edges)
cg.print_cycle()


def DFS(G, k):
	d = [0] * (len(G) + 1)
	mark = [0] * (len(G) + 1)
	pi = [0] * (len(G) + 1)
	back_edge = [0] * 2
	back_edge[0] = back_edge[1] = -1
	for i in range(len(G)):
		if mark[i] == 0:
			pi[i] = -1
			DFS_VISIT(G, i, mark, d, pi, k, back_edge)
		if back_edge[0] != -1 and back_edge[1] != -1:
			break
	current = back_edge[0]
	cycle = []
	while current != pi[back_edge[1]]:
		cycle.append(current)
		current = pi[current]
	return cycle

def DFS_VISIT(G, u, mark, d, pi, k, back_edge):
	current = u
	while current != -1:
		mark[current] = 1
		done = 1
		for i in range(len(G[current])):
			if mark[G[current][i]] == 0:
				done = 0
				pi[G[current][i]] = current
				d[G[current][i]] = d[current] + 1
				current = G[current][i]
				break
			elif d[current] - d[G[current][i]] + 1 >= k + 1:
				back_edge[0] = current
				back_edge[1] = G[current][i]
		if done == 1:
			current = pi[current]

def main():
	(n, m, k) = [int(i) for i in input().split()]
	G = [[] for _ in range(n)]
	for j in range(m):
		(u, v) = [int(d) for d in input().split()]
		G[u - 1].append(v - 1)
		G[v - 1].append(u - 1)
	cycle = DFS(G, k)
	print(len(cycle))
	s = ' '.join((str(u + 1) for u in cycle))
	print(s)
main()


from collections import defaultdict as dd
vis = [0] * 200001
g = dd(list)
(n, m, k) = map(int, input().split())
for _ in range(m):
	(v, j) = map(int, input().split())
	g[v].append(j)
	g[j].append(v)
ans = [1]
while 1:
	vis[ans[-1]] = 1
	for i in g[ans[-1]]:
		if not vis[i]:
			ans.append(i)
			break
	else:
		t = set(g[ans[-1]])
		for i in range(len(ans)):
			if ans[i] in t:
				print(len(ans) - i)
				exit(print(*ans[i:]))


from __future__ import print_function
import sys
from collections import defaultdict
DEBUG = '-d' in sys.argv

def debug(*args, **kwargs):
	if DEBUG:
		print(*args, file=sys.stderr, **kwargs)
	return None

def main():
	(n, m, k) = map(int, input().split())
	graph = defaultdict(list)
	for i in range(0, m):
		(s, t) = map(int, input().split())
		graph[s].append(t)
		graph[t].append(s)
	i = 1
	l = 1
	res = []
	visited = [False] * (n + 1)
	while True:
		visited[i] = True
		res.append(i)
		for e in graph[i]:
			if not visited[e]:
				i = e
				l += 1
				break
		if visited[i]:
			for j in range(0, l + 1):
				if i in graph[res[j]]:
					print(l - j)
					print(' '.join([str(x) for x in res[j:l]]))
					sys.exit(0)
main()


(n, m, k) = map(int, input().split())
from collections import defaultdict
graph = defaultdict(list)
for i in range(0, m):
	(s, t) = map(int, input().split())
	graph[s].append(t)
	graph[t].append(s)
i = 1
l = 1
res = []
visited = [False] * (n + 1)
while True:
	visited[i] = True
	res.append(i)
	for e in graph[i]:
		if not visited[e]:
			i = e
			l += 1
			break
	if visited[i]:
		for j in range(0, l + 1):
			if i in graph[res[j]]:
				print(l - j)
				print(' '.join([str(x) for x in res[j:l]]))
				exit(0)


import sys
import threading

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

def dfs(i, h):
	vis[i] = h
	done[i] = 1
	element.append(i)
	for j in graph[i]:
		if vis[j] != 0 and h - vis[j] >= k:
			ind = element.index(j)
			ans.extend(element[ind:])
			raise ValueError
		elif done[j] == 0:
			dfs(j, h + 1)
	vis[i] = 0
	element.pop()

def solve():
	try:
		for i in range(1, n + 1):
			if done[i] == 0:
				dfs(i, 1)
	except:
		print(len(ans))
		print(*ans)
(n, m, k) = put()
graph = [[] for _ in range(n + 1)]
for i in range(m):
	(x, y) = put()
	graph[x].append(y)
	graph[y].append(x)
(done, vis) = ([0] * (n + 1), [0] * (n + 1))
(element, ans) = ([], [])
max_recur_size = 10 ** 5 * 2 + 1000
max_stack_size = max_recur_size * 500
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=solve)
thread.start()


def f():
	(n, m, k) = map(int, input().split())
	p = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		p[a].append(b)
		p[b].append(a)
	(t, r) = ([0] * (n + 1), [1])
	x = t[1] = 1
	i = 0 - k
	while True:
		for y in p[x]:
			if t[y] == 2:
				return r[r.index(y):]
			if t[y]:
				continue
			(t[y], x) = (1, y)
			r.append(x)
			i += 1
			if i >= 0:
				t[r[i]] = 2
			break
t = f()
print(len(t))
print(' '.join(map(str, t)))


import random

def solve(G, k):
	(d, mark, pi) = [[0] * (len(G) + 1) for _ in range(3)]
	back_edge = [-1] * 2
	pi[0] = -1
	DFS_VISIT(G, 0, mark, d, pi, k, back_edge)
	current = back_edge[0]
	cycle = []
	while current != pi[back_edge[1]]:
		cycle.append(current)
		current = pi[current]
	return cycle

def DFS_VISIT(G, u, mark, d, pi, k, back_edge):
	current = u
	while current != -1:
		mark[current] = 1
		done = 1
		for i in range(len(G[current])):
			if mark[G[current][i]] == 0:
				done = 0
				pi[G[current][i]] = current
				d[G[current][i]] = d[current] + 1
				current = G[current][i]
				break
			elif d[current] - d[G[current][i]] + 1 >= k + 1:
				back_edge[0] = current
				back_edge[1] = G[current][i]
		if done == 1:
			current = pi[current]
	return

def case_generator():
	n = random.randint(3, 10000)
	k = random.randint(2, n)
	G = [[] for _ in range(n)]
	for i in range(len(G)):
		degree = random.randint(k, n)
		nodes = []
		for j in range(n):
			if j != i and (not G[i].__contains__(j)):
				nodes.append(j)
		for j in range(len(G[i]), degree):
			node = random.randint(0, len(nodes))
			G[i].append(nodes[node])
			G[nodes[node]].append(i)
			nodes.remove(nodes[node])
	return (G, k)

def main():
	(n, m, k) = [int(i) for i in input().split()]
	G = [[] for _ in range(n)]
	for j in range(m):
		(u, v) = [int(d) for d in input().split()]
		G[u - 1].append(v - 1)
		G[v - 1].append(u - 1)
	cycle = solve(G, k)
	print(len(cycle))
	s = ' '.join((str(u + 1) for u in cycle))
	print(s)

def random_cases_tester():
	(G, k) = [i for i in case_generator()]
	cycle = solve(G, k)
	print(len(cycle))
	s = ' '.join((str(u + 1) for u in cycle))
	print(s)
	return
main()


(n, l, k) = map(int, input().split())
c = list(([] for i in range(n + 1)))
for i in range(l):
	(x, y) = map(int, input().split())
	c[x].append(y)
	c[y].append(x)
d = list((0 for i in range(n + 1)))
d[1] = 1
now = 1
time = 1
f = True
while f:
	time += 1
	v = 0
	while v >= 0:
		if d[c[now][v]] == 0:
			now = c[now][v]
			d[now] = time
			v = -1
		elif d[c[now][v]] + k < time:
			f = False
			mintime = d[c[now][v]]
			v = -1
		else:
			v += 1
g = list((0 for i in range(time - mintime)))
for i in range(n + 1):
	if d[i] >= mintime:
		g[d[i] - mintime] = i
print(time - mintime)
print(*g)