AT_abc397_g [ABC397G] Maximize Distance

[problemUrl]: https://atcoder.jp/contests/abc397/tasks/abc397_g 给定一个包含 $N$ 个顶点和 $M$ 条边的有向图。顶点编号为 $1,2,\dots,N$，其中第 $j$ 条边（$j=1,2,\dots,M$）从顶点 $u_j$ 指向顶点 $v_j$。保证从顶点 $1$ 到顶点 $N$ 是可达的。 初始时，所有边的权重均为 $0$。当从 $M$ 条边中恰好选择 $K$ 条边并将其权重改为 $1$ 时，求修改后的图中顶点 $1$ 到顶点 $N$ 的最短距离的最大可能值。

输入通过标准输入给出，格式如下： > $N$ $M$ $K$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_M$ $v_M$

输出答案。

### 约束条件 - $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$ 是可达的 - 输入均为整数 ### 样例解释 1 若选择边 $1$ 和 $3$，则顶点 $1$ 到顶点 $3$ 的最短距离为 $1$。由于不存在使最短距离达到 $2$ 或更大的选择方式，因此答案为 $1$。 ### 样例解释 2 若选择边 $1$、$2$ 和 $4$，则顶点 $1$ 到顶点 $4$ 的最短距离为 $2$。由于不存在使最短距离达到 $3$ 或更大的选择方式，因此答案为 $2$。 ### 样例解释 3 请注意图中可能存在多重边。 翻译由 DeepSeek R1 完成