Limits 1s, 512 MB

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 NNplayers have started playing the games. These players have already played against each other. So a total of N(N1)/2N * (N - 1) / 2 rounds have completed. If you enter the tournament now, you’ll have to play against each of these NNplayers. 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 NNplayers is a number from [1,N][1, N] with a larger value indicating a stronger player.

It is guaranteed that at least one valid assignment of relative strengths for the players exists.

Input

The first line of input contains a single integer t(1t100)t ( 1 \le t \le 100 ) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer N(1N1000)N ( 1 \le N \le 1000)— the number of bots currently participating in the tournament.

Each of the next N(N1)/2N * ( N - 1 ) / 2 lines contain the description of a match.

Each match is described by 3 integers: xi,yi,wi(1xi,yiN,0wiN)x_i, y_i, w_i ( 1 \le x_i , y_i \le N , 0 \le w_i \le N) where xix_iand yiy_i are the ids of the players participating in the ithi^{th} game and wiw_i is the id of the winning player. In case of ties, wi=0w_i = 0.

Each player appears in exactly N1N-1 matches against N1N-1 different opponents.

The sum of NN over all test cases does not exceed 10001000.

Output

For each test case, print one line containing an array SS containing NN space-separated integers.

The ithi^{th} element of the array - Si(1SiN)S_i ( 1 \le S_i \le N) is the relative strength of the ithi^{th} player. A larger value of SiS_i indicates a stronger player.

If there are multiple such arrays, print the one in which the maximum strength among the NN players is minimized.

Sample

InputOutput
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


Submit

Login to submit.

Contributors

Statistics

76% Solution Ratio
bisnu_sarkarEarliest, Mar '22
steinumFastest, 0.0s
steinumLightest, 7.3 kB
Shahriar.699347Shortest, 742B
Toph uses cookies. By continuing you agree to our Cookie Policy.