Paintball

Marek and his classmates finished their university studies and celebrated with a game of paintball. After an hour something odd happened: every player had exactly one bullet left. Marek got curious and wanted to know whether every player can be hit exactly once, assuming nobody moves.

The situation at the moment when each player has one bullet is given as a list of pairs of players who can see each other. If a player can see another player, he can fire at him. Choose a target for every player so that every player is hit exactly once.

In other words, player $i$ picks one player he can see as his target, and every player is picked as a target exactly once.

The first line contains two space separated integers $N$ and $M$ ($2 \le N \le 1000$, $0 \le M \le 5000$), where $N$ is the number of players and $M$ is the number of pairs who can see each other. Players are numbered $1$ through $N$.

Each of the next $M$ lines contains two space separated integers $A$ and $B$ ($1 \le A < B \le N$), meaning that players $A$ and $B$ can see each other. No pair is given more than once.

If no assignment of targets hits every player exactly once, print Impossible on the first line.

Otherwise print $N$ lines. The $i$-th line holds the number of the target of player $i$. If several assignments work, print the one whose sequence (target of player $1$, target of player $2$, ..., target of player $N$) is lexicographically smallest.