For technical reasons, some programming languages (Kotlin, C #) will not be available during round 877.
×

No tag edit access

D. Cycle in Graph

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou'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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/24/2017 14:19:18 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|