题目描述

小红有一张联通无向图，她希望找到这张图的一棵生成树，使得1号点和n号点的度数绝对值之差尽可能大。请你帮助她找到这样一棵生成树 对于一张图，选择其中n-1条边，使得所有顶点联通，这些边一定会组成一棵树，即为这张图的一棵生成树。可以证明，图中存在至少一棵生成树。

输入描述

第一行输入两个整数n和m(1 <= n, m <= 1e5)代表图的点数和边数；

此后m行，每行输入两个整数u, v(1 <= u, v <= n; u ≠ v)表示节点u和v之间存在一条边。输入保证图联通且没有重边。

输出描述

在一行上输出n - 1个整数，表示生成树边的编号，这里的编号为顺序输入，且从1开始编号。

如果有多种合法方案，按边的出现顺序输出字典序最小的一种方案。例如：我们选择保留的边的编号分别为[1, 3, 4] 和 [1, 2, 4]这两种方案都是满足题意的，字典序小的意思就是选择后者。

在下面的样例中：编号为1的边是1 2，编号为2的是1 3，……，依此类推。

输入示例

4 4
1 2
1 3
1 4
2 3

输出示例

1 2 3

提示信息

选择前三条边，1号点的度数为 3，4号点的度数为 1，差值的绝对值为2。

时间限制：c/c++：1s；go：3s；java：9s；其他语言：6s。