描述

有一个旅游景区包含 N 个景点，编号为 1 到 N，其中编号为 N 的景点是游客服务中心。
景区中有 M 条双向连接路线，每条路线连接两个景点。

你的任务是：对于编号 1 到 N-1 的每个景点，计算它到达游客服务中心（编号为 N）至少需要经过多少条路线。
如果某个景点无法到达服务中心，则输出 -1。

输入输出格式

输入

第一行输入两个正整数 N 和 M（4 ≤ N ≤ 100，1 ≤ M ≤ 100），表示景点数量和路线数量。
接下来的 M 行，每行两个整数 S 和 E（1 ≤ S, E ≤ N，S ≠ E），表示景点 S 和景点 E 之间有一条双向连接路线。

输出

输出一行包含 N-1 个整数，按编号顺序依次输出景点 1 到 N-1 到达景点 N 所需经过的最少路线条数，如果无法到达则输出 -1。数字之间用空格分隔。

样例数据

5 4
1 2
1 3
2 4
2 5

2 1 3 2

样例解释 • 景点 1 → 2 → 5（2 条路线） • 景点 2 → 5（1 条路线） • 景点 3 → 1 → 2 → 5（3 条路线） • 景点 4 → 2 → 5（2 条路线）