Ankica and Branko’s Pursuit Game

Two players, Ankica and Branko, play a chase game on an undirected connected graph. The game is played in rounds; in each round the following two steps occur:

1. Ankica guesses a vertex at which she believes Branko is currently located. If her guess is correct – that is, if Branko’s position at the beginning of the round equals her guess – the game immediately ends.
2. If the guess is wrong, Branko moves along one edge to a neighboring vertex (note that he is not allowed to stay put).

Formally, let Ankica’s guess‐strategy be \(A=(a_1,a_2,\dots,a_k)\), where \(a_i\) is the vertex guessed in round \(i\). Let Branko’s positions (before moving in each round) be given by \(B=(b_1,b_2,\dots,b_k)\) with the constraint that for every \(1\le i<k\), vertices \(b_i\) and \(b_{i+1}\) are adjacent. The strategy \(A\) is winning if and only if, for every possible legal choice of \(B\) (that is, regardless of Branko’s initial vertex and how he moves), there exists an index \(i\) with \(1\le i\le k\) such that \(a_i=b_i\).

If a winning strategy exists then Ankica must output one with the minimum possible number of rounds. Otherwise, output -1.

Note: All mathematical formulas are written in \(\LaTeX\) format; for example, \(A=(a_1,a_2,\dots,a_k)\) and \(b_i\) denote the guess sequence and Branko’s positions respectively.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1\le n\le15,\;0\le m\le\frac{n(n-1)}{2})\) representing the number of vertices and edges of the graph. The vertices are numbered from 1 to \(n\). It is guaranteed that the graph is connected.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) \((1\le u,v\le n,\;u\neq v)\) indicating there is an undirected edge between vertices \(u\) and \(v\).

outputFormat

If a winning predetermined guessing strategy exists, on the first line output \(k\) – the minimum number of rounds needed. On the second line output \(k\) integers representing the guessed vertices (in order). Otherwise, simply output -1.

sample

1 0

1
1