题目背景

翻译自 CSES-2130 题。

题目描述

一个游戏包含了 $n$ 个房间和 $m$ 个传送门。每天游戏开始时，你从房间 $1$ 出发，目标是到达房间 $n$。

你在游戏中每个传送门最多只能使用一次。你希望在游戏中玩 $k$ 天，每次使用任何传送门都需要支付一个金币。问题是，在最优的情况下，$k$ 天内你需要支付的最少金币数是多少？

输入格式

第一行包含三个整数 $n$、$m$、$k$，分别表示房间的数量、传送门的数量以及你玩游戏的天数。房间编号从 $1$ 到 $n$。

接下来的 $m$ 行中，每行描述一个传送门，包含两个整数 $a$ 和 $b$，表示有一个传送门可以从房间 $a$ 到房间 $b$。

输出格式

首先输出一个整数，表示在最优情况下，你需要支付的最少金币数。

然后，输出 $k$ 条路径描述，按照示例格式。你可以输出任意一个有效的路径方案。

如果无法在 $k$ 天内完成游戏，输出 $-1$。

样例

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

数据范围

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