题目描述

有一个旅游景区，景区中有 N 个景点，景点以数字 1 到 N 编号，其中编号为 N 的景点为游客服务中心所在地。景区中有 M 条连接路线，每条路线连接两个景点。

已知：

1）一个景点可以被多条路线连接；

2）景点之间的连接路线都可以双向行走；

当给出 N 个景点和 M 条连接路线，及 M 条路线的连接关系，请你计算出从编号 1 到编号 N-1 的每一个景点，到达游客服务中心至少需要经过几条路线，如果某个景点不能到达游客服务中心则输出 “-1” 。

例如：N=5，M=4，4 条路线的连接关系为：1<->2、1<->3、2<->4、2<->5，

景点 1 到达景点 5 （游客服务中心）至少经过 2 条路线（路线 2 ，路线 4 ）；

景点 2 到达景点 5（游客服务中心）至少经过 1 条路线（路线 4 ）；

景点 3 到达景点 5（游客服务中心）至少经过 3 条路线（路线 1 ，路线 2 ，路线 4 ）；

景点 4 到达景点 5（游客服务中心）至少经过 2 条路线（路线 3 ，路线 4 ）。

输入格式

第一行输入两个正整数 N 和 M（ 4 ≤ N ≤ 100，1 ≤ M ≤ 100 ），N 表示景点个数，M 表示路线条数，两个正整数之间一个空格隔开。

接下来输入 M 行，每行包含两个正整数 S，E（ 1 ≤ S ≤ N ，1 ≤ E ≤ N，S≠E ），两个正整数之间一个空格隔开，表示编号 S 和编号 E 的两个景点有一条路线连接。

输出格式

一行输出多个整数。按照 1 到 N-1 的编号顺序，分别输出每个景点到达编号 N（游客服务中心），至少经过几条路线可以到达，如果某个景点不能到达则输出 “-1” ，整数之间一个空格隔开。

样例

5 4
1 2
1 3
2 4
2 5

2 1 3 2