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

Constraints

* $1 \leq n \leq 100$

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

Example

Input

4
1 2 2 4
2 1 4
3 0
4 1 3


Output

1 0
2 1
3 2
4 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

/**
 * Graph I - Breadth First Search
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while ((line = br.readLine()) != null && !line.isEmpty()) {
			int n = Integer.parseInt(line);
			Graph1 g = new Graph1(n);
			for (int i = 0; i < n; i++) {
				g.add(br.readLine());
			}
			g.bfs(1);
			for (int i = 1; i <= n; i++) {
				System.out.print(g.get(i).printDistance());
			}
		}
	}
}

class Graph1 {

	private ArrayList<Vertex> vertexs;
	private int[] indexes;
	private LinkedList<Vertex> queue;

	public Graph1(int n) {
		vertexs = new ArrayList<Vertex>();
		indexes = new int[n + 1];
		queue = new LinkedList<Vertex>();
	}

	public void add(String info) {
		int id;
		int[] edge;
		String[] _edge;

		StringTokenizer st = new StringTokenizer(info);
		id = Integer.parseInt(st.nextToken());
		_edge = new String[Integer.parseInt(st.nextToken())];
		edge = new int[_edge.length];
		for (int i = 0; i < _edge.length; i++) {
			_edge[i] = st.nextToken();
		}
		// Arrays.sort(_edge);
		for (int i = 0; i < edge.length; i++) {
			edge[i] = Integer.parseInt(_edge[i]);
		}
		vertexs.add(new Vertex(id, edge));
		indexes[id] = vertexs.size() - 1;
	}

	public Vertex get(int id) {
		return vertexs.get(indexes[id]);
	}

	public void dfs(int t) {
		for (Vertex v : vertexs) {
			t = v.dfs(t);
		}
	}

	public void bfs(int s) {
		Vertex v1, v2;

		get(s).d = 0;
		queue.add(get(s));
		while (!queue.isEmpty()) {
			v1 = queue.removeFirst();
			for (int i = 0; i < v1.edge.length; i++) {
				v2 = get(v1.edge[i]);
				if (v2.d == -1) {
					v2.d = v1.d + 1;
					queue.add(v2);
				}
			}
		}
	}

	class Vertex {
		private int id, d, f;
		private int[] edge;

		private Vertex(int id, int[] edge) {
			this.id = id;
			d = -1;
			f = 0;
			this.edge = edge;
		}

		private int dfs(int t) {
			if (d == -1) {
				d = ++t;
				for (int i = 0; i < edge.length; i++) {
					t = get(edge[i]).dfs(t);
				}
				f = ++t;
			}
			return t;
		}

		public String printTime() {
			return String.format("%d %d %d\n", id, d, f);
		}

		public String printDistance() {
			return String.format("%d %d\n", id, d);
		}
	}
}