链接: https://cses.fi/problemset/task/2130

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一个游戏由 $n$ 个房间和 $m$ 个传送器组成。每天开始时，你在房间 $1$，并且必须抵达房间 $n$。

在游戏过程中，每个传送器最多只能使用一次。你想恰好玩 $k$ 天。每使用一次传送器，你都要支付一枚硬币。在最优化的情况下，玩 $k$ 天所需支付的最少硬币数是多少？

输入

第一行有三个整数 $n$、$m$ 和 $k$：房间数量、传送器数量和游戏天数。房间编号为 $1,2,\dots,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