시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

1 초 | 256 MB | 9 | 4 | 4 | 66.667% |

Prince Potemkin is well-known for his fake villages, created in haste to impress visiting dignitaries. He would lead the delegation along a closed route in his territory, and at each suitable site, a troupe of actors would erect a mobile village and pretend to be its inhabitants. Once the delegation moved, the actors disassembled the village and rushed ahead of the delegation to the next suitable site.

Of course, choosing the right route requires some thought. The members of the delegation occasionally leave the planned route for short inspection trips, and if they ever came back to a site they previously visited, the ruse would fail, since they would see an empty spot where they previously saw a village. Also, to properly impress, the route should pass through at least four sites.

You are given a map of Potemkin’s territory, including the list of bidirectional direct roads among the suitable sites (the crossings among the direct roads are handled by an intricate system of overpasses, making it impossible for the dignitaries to switch from one road to another at any point other than its ends). Prince Potemkin asked you to find a sequence s_{1}, . . . , s_{m} of sites such that:

- m ≥ 4,
- all sites are different (that is, s
_{i}≠ s_{j}for all i ≠ j), - s
_{i}is joined to s_{i+1}by a direct road for i = 1, . . . , m − 1, and s_{m}is joined to s_{1}by a direct road, and - there are no other direct roads among the sites in the sequence (i.e., for all i < j such that j ≠ i + 1 and either i ≠ 1 or j ≠ m, the sites s
_{i}and s_{j}are not joined by a direct road).

A description of the map is read from the standard input. The first line of the input contains two non-negative integers N and R (0 ≤ N ≤ 1 000, 0 ≤ R ≤ 100 000), denoting the number of sites and the number of direct roads among them, respectively. The i-th of the following R lines contains two distinct positive integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ N), showing that the sites ai and bi are joined by a direct road. Each two sites are joined by at most one road.

To the standard output, write a sequence s_{1}, . . . , s_{m} of pairwise distinct integers separated by spaces, describing a route as specified in the problem statement (an arbitrary one, if more valid sequences exist). If no such sequence exists, write “no” instead.

5 6 1 2 1 3 2 3 4 3 5 2 4 5

2 3 4 5

4 5 1 2 2 3 3 4 4 1 1 3

no