CSES - Distinct Routes II
  • Time limit: 1.00 s
  • Memory limit: 512 MB

A game consists of n rooms and m teleporters. At the beginning of each day, you start in room 1 and you have to reach room n.

You can use each teleporter at most once during the game. You want to play the game for exactly k days. Every time you use any teleporter you have to pay one coin. What is the minimum number of coins you have to pay during k days if you play optimally?


The first input line has three integers n, m and k: the number of rooms, the number of teleporters and the number of days you play the game. The rooms are numbered 1,2,\dots,n.

After this, there are m lines describing the teleporters. Each line has two integers a and b: there is a teleporter from room a to room b.

There are no two teleporters whose starting and ending room are the same.


First print one integer: the minimum number of coins you have to pay if you play optimally. Then, print k route descriptions according to the example. You can print any valid solution.

If it is not possible to play the game for k days, print only -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


1 2 4 8 
1 3 5 8