Capped Maximum Disjoint Paths in a DAG

Given a directed acyclic graph (DAG) with n nodes and m edges, where each edge has a capacity of 1, for every node i (except node 1) let f_i be the maximum flow (i.e. maximum number of edge-disjoint paths) from node 1 to node i. For a given integer k, output min\{f_i,\ k\} for every node i from 2 to n.

The maximum flow f_i in this context is equal to the maximum number of edge-disjoint paths from node 1 to node i because each edge can only carry one unit of flow. Note that multiple paths may share vertices, but no edge can be used in more than one path.

Input Format (see below):

• The first line contains three integers: n, m, and k.
• Each of the next m lines contains two integers u and v, representing a directed edge from node u to node v.

Output Format: Output n-1 integers separated by spaces, where the i^th integer (for i from 2 to n) is min\{f_i,\ k\}.

Note: The graph is a DAG, which guarantees there are no cycles.

inputFormat

The first line contains three integers n, m, and k (2 ≤ n ≤ 100 possibly, m small as well for this problem) separated by spaces. Each of the next m lines contains two integers u and v describing a directed edge from node u to node v.

outputFormat

Output a single line containing n-1 integers. The i^th integer (starting from node 2) should be min\{f_i,\ k\} where f_i is the maximum number of edge-disjoint paths from node 1 to node i in the graph.

sample

4 4 1
1 2
1 3
2 4
3 4

1 1 1