题目描述

输入一个边权为1的无向图，输出从1到其他所有点的最短路长度。

输入格式

一行两个整数N，M，为图的顶点和边数。（1≤10^6, 1≤M≤10^6）;

接下来M行，每行两个整数x，y，表示有一条顶点x连向顶点y的边，注意可能有自环和重边。

输出格式

共N行，每行一个非负整数，第i行输出从顶点1到顶点i最短路的长度，如果无法到达顶点i则输出-1。

样例

输入数据 1

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

输出数据1

0
1
1
2
3