Afanasy 有一个简单的连通无向图。Afanasy 在这个图上玩一个游戏。最初，一个筹码位于顶点 1。Afanasy 可以沿着图的边任意移动筹码：在任何时刻，他都可以选择与当前顶点相邻的任何边，包括已经访问过的边，或者他上一步刚刚经过的边。

筹码每经过 $k$ 条边，该边就会被染色（即在第 $k$ 步、第 $2k$ 步等经过的边会被染色）。如果 Afanasy 试图给一条已经染过色的边染色，他就会输。为了获胜，他需要给图中的所有边各染色一次。请帮助 Afanasy 获胜，并找到一个筹码的移动序列，使得所有边都被恰好染色一次，或者确定这是不可能的。

输入格式

第一行包含三个整数 $n, m, k$：图的顶点数、边数以及给定的参数 ($1 \le n \le 100\,000$, $n - 1 \le m \le 100\,000$, $1 \le k \le 10$)。

接下来的 $m$ 行描述了图的边。每行包含两个不同的整数 $u$ 和 $v$：由边连接的两个顶点 ($1 \le u, v \le n$)。

保证图是连通的，且不包含重边和自环。

输出格式

如果没有合适的路径，输出一个整数 $-1$。否则，在第一行输出一个整数：路径上的顶点数。在下一行，按访问顺序输出这些顶点的编号。

路径包含的顶点数不能超过 $1\,000\,001$。路径必须从顶点 1 开始，可以在任意顶点结束。如果存在多条合适的路径，输出其中任意一条即可。

样例

样例输入 1

3 3 1
1 2
2 3
3 1

样例输出 1

4
1 2 3 1

样例输入 2

3 3 2
1 2
2 3
3 1

样例输出 2

7
1 2 3 1 2 3 1