Minimizing the Longest Chain in a DAG via Node Removal

This problem is translated from PA 2018 Round 2 Heros.

Given a directed acyclic graph (DAG) with \(n\) nodes and \(m\) directed edges, your task is to remove exactly \(k\) nodes along with all of their incident edges in order to minimize the length of the longest chain (i.e. path) in the remaining graph.

A chain is defined as a sequence of nodes in which every consecutive pair is connected by a directed edge. The length of a chain is measured by the number of nodes it contains.

inputFormat

The first line contains three integers: \(n\), \(m\), and \(k\) where \(n\) is the number of nodes, \(m\) is the number of edges, and \(k\) is the number of nodes to remove.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) which represent a directed edge from node \(u\) to node \(v\).

outputFormat

Output a single integer representing the minimal possible length of the longest chain (path) in the DAG after exactly \(k\) nodes are removed.

sample

3 3 1
1 2
1 3
2 3

2