Sheikh Abdul really loves football. So you better don't ask how much money he has spent to make famous teams join the annual tournament. Of course, having spent so much money, he would like to see certain teams play each other. He worked out a complete list of games he would like to see. Now it is your task to distribute these games into rounds according to following rules:
- In each round, each remaining team plays at most one game
- If there is an even number of remaining teams, every team plays exactly one game
- If there is an odd number of remaining teams, there is exactly one team which plays no game (it advances with a wildcard to the next round)
- The winner of each game advances to the next round, the loser is eliminated from the tournament
- If there is only one team left, this team is declared the winner of the tournament
As can be proved by induction, in such a tournament with n teams, there are exactly n - 1 games required until a winner is determined.
Obviously, after round 1, teams may already have been eliminated which should take part in another game. To prevent this, for each game you also have to tell which team should win.