Problem 2688 --Graph I - Breadth First Search

2688: Graph I - Breadth First Search

正确率: $0.00\%$ 下一题

Time Limit	$1$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$0$	正确数量	$0$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签	STL

Description

Breadth First Search

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 v1 v2 ... vk

u is ID of the vertex and k denotes its degree.vi are IDs of vertices adjacent to u.

Output

For each vertex u, print id and dd in a line. id is ID of vertex u and dd 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.

Sample Input复制

Sample Output复制

提示

1≤ n≤ 100

赛题来源/所属竞赛会津大学《挑战数据结构与算法》挑战数据结构与算法

竞赛编号	竞赛名称	竞赛时间	访问比赛

AOJ

Please Login

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战