Toll Assignment

King Byteasar has yielded under pressure from merchants and decided to settle the toll issue. In Byteotia, there are (n) towns and (m) bidirectional roads connecting them. Each road connects two distinct towns and no two towns share more than one direct road. Note that roads may traverse tunnels or flyovers. Previously, every town charged duty on every merchant entering or leaving the town. Under the new royal edict, each town is allowed to impose a toll on merchants using exactly one road incident to it (regardless of the direction of travel). Moreover, for any given road, tolls may be imposed by at most one of the two towns that it connects.

Your task is to compute an assignment where every town selects one of its incident roads for toll collection so that no road is used by both endpoints. If no such assignment exists, output (\text{impossible}). Otherwise, output (n) space-separated integers where the (i)-th integer denotes the 1-indexed road assigned to town (i).

inputFormat

The input begins with two integers \(n\) and \(m\): the number of towns and the number of roads.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) (1-indexed) indicating a bidirectional road connecting towns \(u\) and \(v\).

outputFormat

If a valid assignment exists, output \(n\) space-separated integers where the \(i\)-th integer is the index of the road (in the input order, 1-indexed) assigned to town \(i\).

If an assignment is not possible, output impossible.

sample

3 3
1 2
2 3
3 1

1 2 3