407927: GYM102944 D Detroit

A cool thing about Detroit is that it is one of the few places where it is possible to go from the US to Canada by traveling south. You and $$$K$$$ of your Detroit friends have made plans to meet in Detroit at the Ambassador Bridge and cross the border to Windsor, in Canada, to have a dim sum lunch. You will each be traveling from some location in Detroit to the Ambassador Bridge. The road layout in Detroit is very complicated so for this problem we will describe a (fictional) layout by specifying a directed graph with N vertices (or junctions) and M directed edges (or one-way roads). You and your $$$K$$$ friends live at $$$K+1$$$ different junctions in the city. The junctions are numbered from $$$1$$$ to $$$N$$$. Junction $$$1$$$ is the Ambassador Bridge, and you and your friends live at the junctions numbered from $$$2$$$ to $$$K+2$$$.

You and your friends want to use as few roads as possible. Therefore, your task is to design a transportation plan for you and your friends to travel to the Ambassador Bridge that minimizes the number of roads used. That is, you want to find the minimal number of edges you would need so that it is possible to go from each of the junctions $$$2, \ldots, K+2$$$ to junction $$$1$$$ using just those edges.

The first line of the input contains 3 integers: $$$N$$$, $$$M$$$, and $$$K$$$. ($$$3\le K+2\le N\le 20, N-1\le M\le 40$$$)

Then $$$M$$$ lines follow: line $$$i$$$ contains 2 integers $$$u_i$$$ and $$$v_i$$$, indicating a one-way road from junction $$$u_i$$$ to junction $$$v_i$$$.

Output the minimum possible number of edges you and your friends need to travel in order to gather at junction $$$1$$$. You may assume that there is at least one valid plan to do so.

5 5 2
2 1
3 2
4 3
3 5
5 1

3

7 7 2
2 1
6 2
7 6
3 7
4 3
3 5
5 1

4

7 6 1
2 1
3 1
4 1
5 1
6 1
7 1

2

7 7 2
1 2
2 3
3 4
4 1
2 5
6 2
6 7

3