← 返回题目列表

AtCoder · abc397_g

G. 最大化距离

中文机器翻译题面 查看原题

分数: 625 点

问题陈述

给你一个有向图 N 顶点和 M 边缘。顶点已编号 1,2,\dots,N。边缘 j (j=1,2,\dots,M) 从顶点出发 u_j 到顶点 v_j。保证顶点 N 可从顶点到达 1.

最初,所有边都有权重 0。我们准确选择 K 出 M 边并将其权重更改为 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
  • 在给定的图中,顶点 N 可从顶点到达 1.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

请注意,可能存在多边。