题目描述

Afanasy 有一张简单连通无向图。他把一枚棋子放在顶点 $1$ 上，并开始沿着图上的边移动棋子。

每一步，他都可以选择当前顶点相邻的任意一条边走过去。已经走过的边可以再次经过，上一条刚刚走过的边也可以立刻反向走回去。

游戏有一个特殊规则：棋子每经过第 $k$ 条边时，这条边会被染色。也就是说，第 $k,2k,3k,\ldots$ 步所经过的边会被染色。如果某一步试图给一条已经染过色的边再次染色，Afanasy 就输了。

为了获胜，他需要让图中的所有边都恰好被染色一次。

请你帮助 Afanasy 找到一条棋子的移动序列，使所有边恰好被染色一次；如果做不到，请判断无解。

输入格式

第一行包含三个整数 $n,m,k$，分别表示图的顶点数、边数和给定参数。

接下来 $m$ 行，每行包含两个不同的整数 $u,v$，表示顶点 $u$ 和 $v$ 之间有一条无向边。

保证输入图连通，且没有重边和自环。

输出格式

如果不存在满足要求的路径，输出一行一个整数 -1。

否则，第一行输出一个整数，表示路径中的顶点个数。第二行按访问顺序输出这些顶点编号。

路径中的顶点个数不能超过 $1000001$。路径必须从顶点 $1$ 开始，可以在任意顶点结束。如果有多种合法路径，输出任意一种即可。

数据范围

• $1\le n\le 100000$；
• $n-1\le m\le 100000$；
• $1\le k\le 10$；
• $1\le u,v\le n$。

样例 1

输入

3 3 1
1 2
2 3
3 1

输出

4
1 2 3 1

样例 2

输入

3 3 2
1 2
2 3
3 1

输出

7
1 2 3 1 2 3 1