Folded Fixtures

Francis received a popular, sought-after construction toy for her birthday. The toy is a set of metal spheres that can be joined by rigid links of equal length, each link tipped with a magnet at both ends. A link sticks to two spheres and can rotate freely, extending from a sphere in any direction (behaving like a spherical joint), so you can build a wide variety of structures.

Francis has assembled several structures and now wants to store them by hanging them in a corner of her room. She notices that for some structures, when she picks one up and holds it by a single sphere, gravity together with the free-rotating joints makes every link collapse into one thin vertical line (see the figure). Francis hangs a structure by fixing one of its spheres to the ceiling, and to save space she wants to hang each one by the sphere that produces the shortest collapsed line. Any fixture that does not collapse into a single thin line for any choice of sphere takes up too much room, so she discards it.

Figure: one of Francis's constructions (left), the same construction collapsed into a straight-line fixture of length 2 (middle), and a structure that will not collapse into a single line no matter which sphere it hangs from (right). The horizontal gaps drawn between spheres in the middle picture are only for clarity; mathematically the fixture is a single, infinitely thin vertical line.

Treat each metal sphere as an infinitely small point and each link as a line segment of unit length. For a given structure, find the shortest possible length of the collapsed fixture when it is hung by a single sphere, or report that there is no sphere by which it collapses into an infinitely thin straight line.

The input contains several test cases. Each test case describes one fully connected fixture (there are no loose, detached components).

The first line of a test case has two integers $n$ and $m$ separated by a space: the number of spheres ($1 \le n \le 100$) and the number of links ($0 \le m \le 1000$). The spheres are numbered uniquely from $1$ to $n$. Each of the next $m$ lines has two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$), meaning a link connects sphere $a_i$ and sphere $b_i$. Both ends of a link never attach to the same sphere, and no two links connect the same pair of spheres.

A blank line separates consecutive test cases. A line containing "0 0" marks the end of the input and must not be processed.

For each test case, print a single line with the shortest possible length of the collapsed fixture. If the fixture cannot be hung by any single sphere so that it collapses into a straight line, print "impossible" instead.