题目内容

展馆开放前，讲解员要从 $1$ 号门厅出发，把能走到的每个展位都量一遍最短通道。展厅里一共有 $p$ 个展位（编号 $1$ 到 $p$），门厅就是 $1$ 号展位。通道都是双向的，走过一条通道计 1 步，没有额外权值。

馆方要求：对每个从门厅出发能到达的展位，给出最短步数；走不到的展位不用汇报。输出时先按最短步数从小到大排，步数相同再按展位编号从小到大排。

输入描述

第一行两个整数 $p$ 和 $e$（$1\le p\le 10^5$，$0\le e\le 10^5$），表示展位数与通道数。

接下来 $e$ 行，每行两个整数 $a$、$b$（$1\le a,b\le p$），表示展位 $a$ 与 $b$ 之间有一条双向通道。通道可能有重边或自环，计算最短步数时自环可忽略。

输出描述

对每个能从 $1$ 号门厅走到的展位输出一行两个整数：展位编号，以及到门厅的最短步数。行的顺序为：步数升序，步数相同时编号升序。门厅自己的步数为 0。

样例1

输入

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

输出

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

说明

从门厅出发，2、3 都是 1 步，所以 2 写在 3 前面。4 与 6 都是 2 步，按编号先写 4 再写 6。5 要经过 4，共 3 步。

样例2

输入

4 1
2 3

输出

1 0

说明

2 与 3 互相连通，但都到不了门厅，因此只汇报门厅自己。

样例3

输入

3 2
1 3
1 2

输出

1 0
2 1
3 1

说明

边的输入顺序先写到了 3，但相同步数仍须按编号输出，所以 2 在 3 前。

数据范围

• $1\le p\le 10^5$
• $0\le e\le 10^5$
• $1\le a,b\le p$
• 图为无向无权图，允许重边与自环
• 所有编号均为整数