Breadth-First-Search-PATH

Implement Breadth First Search on vertices numbered 0 to V-1. Implement the graph using an adjacency list only.

Input Format

The first input is T, the number of test cases. Thereafter, each test case starts with “V E”, where V is the number of vertices and E is the number of edges. Thereafter, each E line contains “u v” denoting an edge from the vertex u to the vertex v. The source is always taken to be vertex numbered 0.

Output Format

V lines, each printing the PATH from source of the vertex V. If there is no path from source to V, print "NIL".

The edges are prioritized in the order they are input, with an earlier edge in input having a higher priority. The edges must be processed in the same order for any vertex.

Print the path instead of the cost. Print “NIL” if no path exists.

Sample Input

1

7 14

0 5

5 0

0 1

1 0

1 2

2 1

2 5

5 2

0 3

3 0

3 4

4 3

4 5

5 4

Sample Output

0

0 1

0 5 2

0 3

0 5 4

0 5

NIL