Potemkin cycle

Prince Potemkin is known for his fake villages, put up in a hurry to impress visiting dignitaries. He leads a delegation along a closed route through his territory, and at every suitable site a troupe of actors raises a portable village and plays its inhabitants. As soon as the delegation moves on, the actors take the village apart and run ahead to the next site of the route.

Choosing the route takes some care. Members of the delegation sometimes leave the planned route for a short inspection trip, and the trick fails the moment they return to a site they have already seen, because they would find an empty field where a village stood. The route also has to pass through at least four sites to make an impression.

You are given a map of the territory, that is the list of two way direct roads between the suitable sites. An elaborate system of overpasses carries one road over another, so the dignitaries cannot change roads anywhere except at the two ends of a road.

Find a sequence $s_1, \dots, s_m$ of sites such that:

• $m \ge 4$,
• all sites are different, that is $s_i \ne s_j$ for all $i \ne j$,
• a direct road joins $s_i$ and $s_{i+1}$ for $i = 1, \dots, m - 1$, and a direct road joins $s_m$ and $s_1$,
• no other direct road runs between two sites of the sequence, that is $s_i$ and $s_j$ are not joined by a direct road for every $i < j$ with $j \ne i + 1$ and $(i, j) \ne (1, m)$.

The first line has two integers $N$ and $R$ ($0 \le N \le 1000$, $0 \le R \le 100\,000$), the number of sites and the number of direct roads. The sites are numbered 1 to $N$. Each of the next $R$ lines has two different integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$), meaning that a direct road joins the sites $a_i$ and $b_i$. At most one road joins any two sites.

If no sequence satisfies the conditions, print no.

Several sequences usually satisfy the conditions, so print the single one that the following rule picks, on one line, with the site numbers separated by single spaces.

For a site $v$, let $G_v$ be what is left of the map after deleting $v$ together with every site that a road joins to $v$. Two sites $a$ and $b$ form a detour pair of $v$ when a road joins $v$ to $a$, a road joins $v$ to $b$, no road joins $a$ and $b$, and some path leads from $a$ to $b$ whose interior sites all belong to $G_v$.

1. Let $v$ be the smallest site that has a detour pair. If no site has one, print no.
2. Write each detour pair of $v$ as $(a, b)$ with $a < b$. Take the pair with the smallest $a$, and among those the pair with the smallest $b$.
3. Let $H$ be the map restricted to $a$, $b$ and the sites of $G_v$, keeping every road between two of them. Among the shortest paths from $a$ to $b$ in $H$, take the lexicographically smallest one: start at $a$ and always step to the smallest numbered site that keeps the remaining distance to $b$ as small as possible.
4. Print $v$, then $a$, then the interior sites of that path in order, then $b$.

The sequence built this way always satisfies the four conditions, and the rule leaves exactly one answer.