题目描述

你要规划一次最短的公路旅行。

给定一个无向图，点表示景点，边表示道路。旅行必须：

• 从 1 号点出发；
• 至少访问一个其它点；
• 最后回到 1 号点；
• 不能立刻沿着刚刚走过的那条边原路返回。

也就是说，如果你刚刚从 \(x\) 直接走到 \(y\)，那么下一步不能立刻从 \(y\) 沿同一条边回到 \(x\)。
但你可以在更晚的时候再次经过这条边。

请构造一条满足条件且长度（经过的道路条数）最短的旅行路线。

如果不存在这样的路线，输出 impossible。

输入格式

第一行两个整数 \(n, m\)：

• \(2 \le n \le 10^5\)
• \(1 \le m \le 2 \times 10^5\)

分别表示点数和边数。

接下来 \(m\) 行，每行两个整数 \(u, v\)，表示点 \(u\) 和点 \(v\) 之间有一条无向边：

• \(1 \le u < v \le n\)

保证：

• 任意一对点之间最多只有一条边。

输出格式

如果不存在满足条件的旅行路线，输出：

impossible

否则输出一条合法路线：

• 第一行输出一个整数 \(k\)，表示旅行中依次访问的点数（包括起点 1 和终点 1）
• 第二行输出这 \(k\) 个点，表示访问顺序

如果有多种最短合法路线，输出任意一种均可。

样例输入 1

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

样例输出 1

4
1 3 2 1

样例输入 2

12 13
1 2
2 3
1 4
4 5
5 6
6 7
4 7
1 8
8 9
9 10
10 11
11 12
9 12

样例输出 2

7
1 4 5 6 7 4 1

样例输入 3

3 2
1 2
2 3

样例输出 3

impossible

样例输入 4

4 3
2 3
3 4
2 4

样例输出 4

impossible