Given an graph compute its DFS traversal.

The graph has n nodes indexed 0 to n-1. It is given in the form of an adjacency list.

Compute the DFS from the node indexed 0. Follow the order given in the adjacency list when choosing path.

Example

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has the following lines:

• The first line contains the integer n.
• The next n lines descibes the adjacent nodes for the i^th node.
  • The first integer m denotes the number of adjacent nodes.
  • The next m integers denote adjacent nodes.

Output Format

For each test case, the output has one line with space-separated integers denoting the DFS traversal.

Sample Input

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

Expected Output

0 1 2 3
0 1 2 3

Constraints

1 <= T <= 10
1 <= n <= 500
0 <= m < n2