Tournament Game Scheduling

You are given a series of games to be played during a tournament day. Each game is between two players. Your task is to assign each game a period (an integer) such that no player is scheduled in more than one game in the same period. Every game must be played exactly once.

Formally, you are given an integer \(n\) representing the number of games, followed by \(n\) pairs of integers \((a, b)\), where each pair represents a game between players \(a\) and \(b\). For each game, assign the smallest possible period \(p\) (starting from 1) that is not equal to the period of any game in which either player \(a\) or \(b\) has already participated.

Example:

Input:
4
1 2
2 3
3 4
1 3
Output:
1 2 1
2 3 2
3 4 1
1 3 2

</p>

Note: If there are formulas in the problem statement, they are given in \(\LaTeX\) format.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(n\), the number of games.
• The next \(n\) lines each contain two integers \(a\) and \(b\), representing the players involved in each game.

outputFormat

For each game, output a line with three integers \(a\), \(b\), and \(p\) separated by spaces, where \(p\) is the scheduled period for that game. The games should be output in the same order they were given in the input, and the output should be written to stdout.

## sample

4
1 2
2 3
3 4
1 3

1 2 1
2 3 2
3 4 1
1 3 2

</p>