Given a graph compute its BFS.

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

Return the BFS traversal starting at the node indexed 0. Follow the order of nodes as in the adjacency list.

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 BFS.

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 <= n