There is a hidden permutation $p$ of $1 \sim n$ of length $n$. We arrange the elements of $p$ in a circle, meaning that for any integer $k$, $p_k = p_{(k - 1) \bmod n + 1}$.
For each $2 \leq i \leq n$, we are given the set $S_i$ consisting of the $i - 1$ elements that immediately follow the element with value $i$ in $p$. Formally, if $p_k = i$, we are given the set $S_i = \{p_{k+1}, p_{k+2}, \dots, p_{k+i-1}\}$ in arbitrary order.
You need to reconstruct any permutation that satisfies all the conditions. It is guaranteed that a solution exists.
Input
The input contains multiple test cases.
The first line contains an integer $T$ representing the number of test cases.
For each test case:
- The first line contains an integer $n$.
- The next $n - 1$ lines each contain $i$ integers, representing all elements of $S_{i+1}$ for $i = 1, \dots, n-1$.
Output
For each test case, output a single line containing a permutation of length $n$ representing the reconstructed permutation $p$.
Examples
Input 1
6 2 1 3 1 1 2 3 3 1 2 4 4 4 2 3 1 2 8 6 5 7 3 5 7 7 1 8 2 4 3 5 7 1 1 8 2 6 4 3 2 6 4 3 5 7 1 11 1 2 4 8 2 1 9 7 10 6 9 7 4 3 11 4 3 9 11 2 1 5 11 6 3 7 10 9 4 3 11 1 8 5 2 10 2 7 8 3 1 4 6 11 9 7 4 2 6 1 3 5 8 10 9
Output 1
1 2 3 2 1 1 2 3 1 3 2 4 1 8 2 6 4 3 5 7 10 6 7 9 11 3 4 2 1 8 5
Note 1
For the first test case, the only information given is that the element following the value $2$ is $1$, so $p = [1, 2]$ satisfies the condition. Note that $p = [2, 1]$ also satisfies the condition.
For the second test case, other valid permutations include $p = [1, 3, 2]$ and $p = [2, 1, 3]$.
Constraints
This problem uses bundled testing. The special constraints for each subtask are as follows:
- Subtask 1 (13 points): $n \le 10$.
- Subtask 2 (9 points): $n \le 20$.
- Subtask 3 (17 points): $n \le 50$.
- Subtask 4 (21 points): $n \le 100$.
- Subtask 5 (19 points): $n \le 200$.
- Subtask 6 (21 points): No additional constraints.
For all test cases, $1 \le T \le 10$ and $1 \le n \le 1000$. It is guaranteed that a solution exists.