TDBFS - Searching the Graph

For a given list of adjacent vertices of a graph and a chosen vertex v write down in the Depth First Search (DFS) or Breadth First Search (BFS) order all the vertices from the connected component of the graph containing v. Assume that the number of vertices of the graph is at most 1000.

Input


t [the number of graphs <= 100]
Graph:
n [1 <= n <= 1000 the number of graph vertices]
i m a b c ... [the list of m adjacent vertices to vertex i]
Any query is as follows: [not more than n queries]
v i
where 1 <= v <= n is the beginning vertex and i = 0 for DFS order and i = 1 for BFS order.
0 0 [at the end of the serie]

The list for isolated vertex a is a 0.

Output


graph i [test case, word graph is necessary]
a b c ... [the DFS or BFS order of all vertices]

Example

Input:
3
6
1 2 3 4
2 2 3 6
3 2 1 2
4 1 1
5 0
6 1 2
5 1
1 0
1 0
0 0
10
1 6 3 5 6 7 8 9
2 1 9
3 2 1 5
4 5 6 7 8 9 10
5 4 1 3 7 8
6 3 1 4 7
7 5 1 4 5 6 8
8 5 1 4 5 7 10
9 3 1 2 4
10 2 4 8
7 1
1 0
2 1
4 1
7 1
0 0
2
1 0
2 0
1 1
0 0

Output:
graph 1
5
1 3 2 6 4
1 3 2 6 4
graph 2
7 1 4 5 6 8 3 9 10 2
1 3 5 7 4 6 8 10 9 2
2 9 1 4 3 5 6 7 8 10
4 6 7 8 9 10 1 5 2 3
7 1 4 5 6 8 3 9 10 2
graph 3
1


Dodane przez:mima
Data dodania:2004-10-22
Limit czasu wykonania programu:15s
Limit długości kodu źródłowego5000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.