题目描述

一个游戏有 $n$ 个房间和 $m$ 个传送门。每天开始时，你从房间 $1$ 出发，并需要到达房间 $n$。

每天游戏中，每个传送门最多只能使用一次。你希望连续玩恰好 $k$ 天。每次使用任意传送门都要支付 $1$ 枚金币。请在最优游玩方式下，求 $k$ 天总共需要支付的最少金币数，并给出路线。

输入格式

第一行包含三个整数 $n,m,k$，表示房间数量、传送门数量和游玩天数。房间编号为 $1,2,\ldots,n$。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示存在一条从 $a$ 到 $b$ 的传送门。

保证不存在起点和终点都相同的两条传送门。

输出格式

如果可以玩恰好 $k$ 天，先输出一个整数，表示最小金币数；然后按样例格式输出 $k$ 条路线。可以输出任意一种合法最优方案。

如果不可能，输出 -1。

数据范围

• $2 \le n \le 500$
• $1 \le m \le 1000$
• $1 \le k \le n-1$
• $1 \le a,b \le n$

样例

样例输入

8 10 2
1 2
1 3
2 5
2 4
3 5
3 6
4 8
5 8
6 7
7 8

样例输出

6
4
1 2 4 8
4
1 3 5 8