题目背景

翻译自 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 \leq n \leq 500$；

$1 \leq m \leq 1000$；

$1 \leq k \leq n-1$；

$1 \leq a, b \leq n$；