Problem Description

Given a directed acyclic graph with $n$ vertices and $m$ edges, where each edge has a capacity of $1$. For each vertex $i$ other than vertex $1$, let the maximum flow from vertex $1$ to vertex $i$ be $f_i$. Your task is to find $\min\{f_i, k\}$.

On a graph where edge capacities are $1$, a flow from vertex $1$ to vertex $i$ is a path from vertex $1$ to vertex $i$. If there can be at most $f_i$ disjoint flows (i.e., no edge is shared between two flows) from vertex $1$ to vertex $i$, we consider the maximum flow from vertex $1$ to vertex $i$ to be $f_i$.

Input Format

The first line of input contains three integers $n, m, k$ ($2 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5, 1 \leq k \leq 50$), separated by spaces, representing the number of vertices, the number of edges, and the parameter, respectively.

The next $m$ lines each contain two integers $x_i, y_i$ ($1 \leq x_i, y_i \leq n, x_i \neq y_i$), separated by spaces, describing a directed edge.

The graph is guaranteed to have no self-loops, may have multiple edges, and is ensured to be a directed acyclic graph.

Output Format

Output a single line with $n-1$ integers, separated by spaces. For the $i$-th integer, if the maximum flow from vertex $1$ to vertex $i+1$ does not exceed $k$, it is the value of the maximum flow; otherwise, it is $k$.

Sample Input and Output

Sample Input #1

7 12 3
1 2
1 3
3 2
3 4
2 4
1 5
5 6
3 6
1 7
5 7
6 7
4 7

Sample Output #1

2 1 2 1 2 3

Sample Input #2

5 8 50
1 2
1 2
1 2
3 2
2 4
2 4
2 4
2 4

Sample Output #2

3 0 3 0

Notes

The graph described in the first sample is as follows:

We can find 4 disjoint paths from vertex $1$ to vertex $7$:

1->7

1->5->7

1->3->6->7

1->2->4->7

We cannot find more disjoint paths from vertex $1$ to vertex $7$:

Therefore, the maximum flow from vertex $1$ to vertex $7$ is $f_7 = 4$, but since $k = 3$, the sixth integer in the answer is $3$.

见题面 Input 部分

见题面 Output 部分