ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1156. Two Rounds

Time limit: 2.0 second
Memory limit: 64 MB
There are two rounds in the Urals Championship. The competitors have to solve N problems on each round. The jury had been working hard and finally managed to prepare 2N problems for the championship. But it appeared that among those problems there were some, which have the analogous solutions. One shouldn’t assign such a problems for the same round. Please, help the jury form sets of tasks for each of the rounds.


First line contains two numbers: N, the number of tasks for a round, and M, the number of pairs of tasks which should not be assigned for one round (1 ≤ N ≤ 50; 0 ≤ M ≤ 100). Then M lines follow, each of them contains two numbers of analogous tasks.


Output two lines, containing numbers of tasks assigned for each round. If there is no solution, output the only word “IMPOSSIBLE”. If there are more than one solution you may assume anyone of them.


2 3
1 3
2 1
4 3
1 4
2 3
Problem Author: Eugene Bryzgalov
Problem Source: Ural Collegiate Programming Contest, April 2001, Perm, English Round