Potemkin Cycle

Given an undirected graph with N vertices and R edges, find a simple cycle (a cycle with all vertices distinct) whose vertex set, when considered as an induced subgraph of the original graph, contains only the cycle edges (i.e. no extra edges among the cycle vertices apart from the cycle neighbours). In other words, if the cycle is represented as a sequence of vertices s₁, s₂, ..., s_m (with m ≥ 4), the following conditions must hold:

• m ≥ 4.
• All vertices in the sequence are distinct.
• For every i = 1,..., m-1, there is an edge between s_i and s_i+1, and there is an edge between s_m and s₁ (thus forming a cycle).
• The induced subgraph on the vertices {s₁, s₂, ..., s_m} contains no edges other than those of the cycle. That is, for any two vertices which are not consecutive in the cycle (taking s₁ and s_m as consecutive), there is no edge between them in the original graph.

If there are multiple solutions, any valid cycle can be output. If no such cycle exists, output -1.

Note: All formulas are expressed in LaTeX format. For example, \(m \ge 4\) and the vertices set \(\{s_1, s_2, \dots, s_m\}\).

inputFormat

The input begins with two integers N and R — the number of vertices and edges respectively. The vertices are numbered from 1 to N. The next R lines each contain two integers u and v indicating that there is an undirected edge between vertices u and v.

outputFormat

If there exists an induced cycle (as defined) of length at least 4, output a single line containing m followed by m space‐separated integers that represent the vertices of the cycle (in the order they appear in the cycle). The vertices should be output using 1-indexing. If no such cycle exists, output a single line containing -1.

sample

4 4
1 2
2 3
3 4
4 1

4 1 2 3 4