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: interview

Starter code:

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

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)

import sys
import threading

def put():
    return list(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 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()