题目描述

有一个旅游景区，景区中有 $N$ 个景点，景点以数字 $1$ 到 $N$ 编号，其中编号为 $N$ 的景点为游客服务中心所在地。景区中有 $M$ 条连接路线，每条路线连接两个景点。已知：
1）一个景点可以被多条路线连接；
2）景点之间的连接路线都可以双向行走；
当给出 $N$ 个景点和 $M$ 条连接路线，及 $M$ 条路线的连接关系，请你计算出从编号 $1$ 到编号 $N-1$ 的每一个景点，到达游客服务中心至少需要经过几条路线，如果某个景点不能到达游客服务中心则输出 "$-1$"。
例如：$N=5$，$M=4$，$4$ 条路线的连接关系为：$1 \leftrightarrow 2$、$1 \leftrightarrow 3$、$2 \leftrightarrow 4$、$2 \leftrightarrow 5$ 景点$1$ 到达景点$5$（游客服务中心）至少经过 $2$ 条路线（路线$2$、路线$4$）；
景点$2$ 到达景点$5$（游客服务中心）至少经过 $1$ 条路线（路线$4$）；
景点$3$ 到达景点$5$（游客服务中心）至少经过 $3$ 条路线（路线$1$、路线$2$、路线$4$）；
景点$4$ 到达景点$5$（游客服务中心）至少经过 $2$ 条路线（路线$3$、路线$4$）；

输入格式

第一行输入两个正整数 $N$ 和 $M(4 \le N \le 100，1 \le M \le 100)$，$N$ 表示景点个数，$M$ 表示路线条数，两个正整数之间一个空格隔开
接下来输入 $M$ 行，每行包括两个正整数 $S$，$E(1 \le S \le N，1 \le E \le N，S \ne E)$，两个正整数之间一个空格隔开，表示编号$S$ 和编号$E$ 的两个景点有一条路线连接

输出格式

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

样例

输入样例 #1

5 4
1 2
1 3
2 4
2 5

输出样例 #1

2 1 3 2