UVa 10959

Summary

Given an unweighted undirected graph, we're asked the find the distance from a single node (Don Giovanni) to everyone else. This is a simple Single Source Shortest Path (Shortest Path) problem.

Explanation

Since ${\displaystyle N\leq 1000}$, a ${\displaystyle O(N^{2})}$ is optimal in terms of ${\displaystyle N}$ - the input can be ${\displaystyle O(N^{2})}$ - and that is all that is necessary for this problem, though we can do better if we consider the complexity in terms of ${\displaystyle V}$ and ${\displaystyle E}$ - the edges and vertices. We can get the running time to ${\displaystyle O(E+V)}$ using simply breadth-first search.

Notes

This problem is just another disguise for the traditional Erdös numbers.

Input

2

5 6
0 1
0 2
3 2
2 4
4 3
1 2

5 6
0 1
0 2
3 2
2 4
4 3
1 2


Output

1
1
2
2

1
1
2
2