Description

请编写一个程序，求给定的有向图G=(V,E)中顶点1到各顶点的最短路径d（路径边数的最小值）。各顶点编号分别为1至n。如果从顶点1出发无法到达某顶点，则与该顶点的距离记为-1.

Format

Input

第1行输入G的顶点数n。接下来n行按如下n行按如下格式输入各顶点u的邻接表。

u k v1 v2...Vk

其中u为顶点编号，k为u的度，v1 v2 ...vk为与u相邻的顶点编号。

Output

按顶点编号顺序输出各顶点的id、d，每个顶点占1行。id为顶点编号，d为顶点1到该顶点的距离。

限制1<=n<=100

Samples

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

1 0
2 1
3 2
4 1

Limitation

1000ms, 1024KiB for each test case.