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 v1, v2, ..., vd such, that nodes v1 and vd are connected by an edge of the graph, also for any integer i (1 ≤ i < d) nodes vi and vi + 1 are connected by an edge of the graph.

Input

The first line contains three integers n, m, k (3 ≤ n, m ≤ 105; 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 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — 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 v1, v2, ..., vr (1 ≤ vi ≤ 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 
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
            else:
                if 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()
