H. Maximum Flow
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a directed acyclic graph with $$$n$$$ vertices and $$$m$$$ edges with $$$1$$$ capacity. For every vertex $$$i$$$ except vertex $$$1$$$, if the maximum flow from vertex $$$1$$$ to vertex $$$i$$$ is $$$f_i$$$, please output $$$\min\{f_i,\ k\}$$$.

For a graph with edge capacity $$$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 paths from vertex $$$1$$$ to vertex $$$i$$$(i.e. each pair of flows do not share edges), we consider the maximum flow from vertex $$$1$$$ to vertex $$$i$$$ to be $$$f_i$$$.

Input

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.

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.

It is guaranteed that the graph has no self-loops, but may contain multiple edges. It is also guaranteed that the given graph is a directed acyclic graph.

Output

Output a single line containing $$$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$$$, then output the value of the maximum flow; otherwise, output $$$k$$$.

Examples
Input
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
Output
2 1 2 1 2 3
Input
5 8 50
1 2
1 2
1 2
3 2
2 4
2 4
2 4
2 4
Output
3 0 3 0
Note

The graph described in the first example 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 can not find more disjoint paths from vertex $$$1$$$ to vertex $$$7$$$.

So 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$$$.