G - Maximize Distance Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 625 点

問題文

N 頂点 M 辺の有向グラフが与えられます。頂点には 1,2,\dots,N の番号がついており、辺 j (j=1,2,\dots,M) は頂点 u_j から頂点 v_j に向かいます。ここで、頂点 1 から頂点 N に到達可能であることが保証されます。

はじめ、すべての辺の重みは 0 です。M 本の辺からちょうど K 本の辺を選んで重みを 1 に変更するとき、変更後のグラフにおける頂点 1 から頂点 N への最短距離としてあり得る最大値を求めてください。

制約

  • 2 \leq N \leq 30
  • 1 \leq K \leq M \leq 100
  • 1 \leq u_j,v_j \leq N
  • u_j \neq v_j
  • 与えられるグラフにおいて、頂点 1 から頂点 N へ到達可能である
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

3 3 2
1 2
2 3
1 3

出力例 1

1

辺 1,3 を選べば、頂点 1 から頂点 3 への最短距離が 1 になります。最短距離を 2 以上にする選び方は存在しないので、答えは 1 です。

入力例 2

4 4 3
1 2
1 3
3 2
2 4

出力例 2

2

辺 1,2,4 を選べば、頂点 1 から頂点 4 への最短距離が 2 になります。最短距離を 3 以上にする選び方は存在しないので、答えは 2 です。

入力例 3

2 2 1
1 2
1 2

出力例 3

0

多重辺が存在しうることに注意してください。

Score : 625 points

Problem Statement

You are given a directed graph with N vertices and M edges. The vertices are numbered 1,2,\dots,N. Edge j (j=1,2,\dots,M) goes from vertex u_j to vertex v_j. It is guaranteed that vertex N is reachable from vertex 1.

Initially, all edges have weight 0. We choose exactly K out of the M edges and change their weights to 1. Find the maximum possible value of the shortest distance from vertex 1 to vertex N in the resulting graph.

Constraints

  • 2 \leq N \leq 30
  • 1 \leq K \leq M \leq 100
  • 1 \leq u_j, v_j \leq N
  • u_j \neq v_j
  • In the given graph, vertex N is reachable from vertex 1.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the answer.

Sample Input 1

3 3 2
1 2
2 3
1 3

Sample Output 1

1

By choosing edges 1,3, the shortest distance from vertex 1 to vertex 3 becomes 1. There is no way to make the shortest distance 2 or greater, so the answer is 1.

Sample Input 2

4 4 3
1 2
1 3
3 2
2 4

Sample Output 2

2

By choosing edges 1,2,4, the shortest distance from vertex 1 to vertex 4 becomes 2. There is no way to make the shortest distance 3 or greater, so the answer is 2.

Sample Input 3

2 2 1
1 2
1 2

Sample Output 3

0

Note that there may be multi-edges.