You were idly scrolling through your Phesbook feed one morning when you discovered an ongoing event called “A Game of Bots”. It turns out to be an AI contest where participants have to build their own AI agents and win against opponents’ agents in matches of chess.
You can see the tournament has already begun and players have started playing the games. These players have already played against each other. So a total of rounds have completed. If you enter the tournament now, you’ll have to play against each of these players. So you want to have an idea about their strength.
From your experiences, you know that in these games a stronger bot always wins against a weaker bot. If both the participating bots in a game have similar strengths, the game is tied.
You can easily find out the results of the previous matches from the event page. Can you determine the relative strength of the participating players from these results?
Here, the relative strength of each of the players is a number from with a larger value indicating a stronger player.
It is guaranteed that at least one valid assignment of relative strengths for the players exists.
The first line of input contains a single integer — the number of test cases. Description of the test cases follows.
The first line of each test case contains an integer — the number of bots currently participating in the tournament.
Each of the next lines contain the description of a match.
Each match is described by 3 integers: where and are the ids of the players participating in the game and is the id of the winning player. In case of ties, .
Each player appears in exactly matches against different opponents.
The sum of over all test cases does not exceed .
For each test case, print one line containing an array containing space-separated integers.
The element of the array - is the relative strength of the player. A larger value of indicates a stronger player.
If there are multiple such arrays, print the one in which the maximum strength among the players is minimized.
Input | Output |
---|---|
2 3 1 2 2 1 3 3 2 3 3 4 1 2 2 3 4 3 1 3 3 2 3 3 1 4 0 2 4 2 | 1 2 3 1 2 3 1 |
In the second test case, player 1 has strength 1, and player 2 has strength 2. So player 2 wins the first match. The 5th match ties since player 1 and player 4 have the same strength |