#P16140. [Cses2130]Distinct Routes II

[Cses2130]Distinct Routes II

题目描述

一个游戏有 nn 个房间和 mm 个传送门。每天开始时,你从房间 11 出发,并需要到达房间 nn。

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

输入格式

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

接下来 mm 行,每行包含两个整数 a,ba,b,表示存在一条从 aa 到 bb 的传送门。

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

输出格式

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

如果不可能,输出 -1。

数据范围

  • 2≤n≤5002 \le n \le 500
  • 1≤m≤10001 \le m \le 1000
  • 1≤k≤n−11 \le k \le n-1
  • 1≤a,b≤n1 \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