TDBFS - Searching the Graph

no tags 

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


hide comments
martinho_11235: 2018-10-18 01:39:54

Good problem for those that are starting to solve BFS and DFS problem...

Last edit: 2018-10-18 01:40:36
kamran siddique: 2016-04-08 21:44:34

1st Go :)

Amir Najjar: 2016-03-08 17:26:30

AC on first submit
Just make sure u visit the smaller indexed node first.

sabri: 2016-03-02 20:26:38

may someone explain this prolbleù statment??

bourne: 2016-02-27 09:53:53

would any DFS solution not work? Do we necessarily need to order them according to input?

Nehal J Wani: 2015-12-07 11:16:07

"[not more than n queries]" is a lie.

hashem sllat: 2015-10-16 17:18:19

cake of piece :D

ericleoo: 2015-07-03 20:41:01

This problem is not clear at all

Kishlay Raj: 2014-10-31 00:38:37

in dfs its pushing the nodes in reverse order i.e. the one with higher value get pushed first

LeppyR64: 2014-10-31 00:38:37

Use a preorder traversal. Order the edges on the order they are input.

Last edit: 2011-11-25 16:22:25

Added by:mima
Date:2004-10-22
Time limit:15s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All