Problem Description

This problem is translated from PA 2018 Round 2 Heros.

Given a directed acyclic graph with $n$ nodes and $m$ directed edges.

You need to delete $k$ nodes and all edges incident to them, so that the length of the longest path in the graph is as small as possible.

Input Format

The first line contains three integers $n$, $m$, and $k$.

The next $m$ lines each contain two integers $x$ and $y$, indicating that there is a directed edge from node $x$ to node $y$.

Output Format

Output one integer in one line, the minimum possible length of the longest path in the graph.

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

2

3 3 3
1 2
1 3
2 3

0

Hint

Explanation for Sample 1

After deleting node $4$, the length of the longest path in the graph is $2$. This is the minimum value we can achieve. You can verify that among all possible choices, the minimum possible longest-path length is $2$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata:

• $1 \le n \le 300$
• $0 \le m \le 400$
• $0 \le k \le \min(n,4)$
• $1 \le x < y \le n$

Translated by ChatGPT 5