8480: ALDS1_11_C : Breadth First Search
[Creator : ]
Description
Write a program which reads an directed graph $G=(V,E)$, and finds the shortest distance from vertex $1$ to each vertex (the number of edges in the shortest path). Vertices are identified by IDs $1,2,...n$.
Input
In the first line, an integer $n$ denoting the number of vertices, is given.
In the next $n$ lines, adjacent lists of vertex $u$ are given in the following format:
$u\ k\ v_1\ v_2\ \cdots\ v_k$
$u$ is ID of the vertex and $k$ denotes its degree. $v_i$ are IDs of vertices adjacent to $u$.
In the next $n$ lines, adjacent lists of vertex $u$ are given in the following format:
$u\ k\ v_1\ v_2\ \cdots\ v_k$
$u$ is ID of the vertex and $k$ denotes its degree. $v_i$ are IDs of vertices adjacent to $u$.
Output
For each vertex $u$, print id and $d$ in a line. id is ID of vertex $u$ and $d$ is the distance from vertex $1$ to vertex $u$.
If there are no path from vertex $1$ to vertex $u$, print $-1$ as the shortest distance. Print in order of IDs.
If there are no path from vertex $1$ to vertex $u$, print $-1$ as the shortest distance. Print in order of IDs.
Constraints
$1 \leq n \leq 100$
Sample 1 Input
4
1 2 2 4
2 1 4
3 0
4 1 3
Sample 1 Output
1 0
2 1
3 2
4 1
