P10698 [SNCPC2024] Maximum Flow.

Given a directed acyclic graph with $n$ vertices and $m$ edges, where the capacity of each edge is $1$. For every vertex $i$ except vertex $1$, let the maximum flow from vertex $1$ to vertex $i$ be $f_i$. Compute $\min\{f_i,\ k\}$. In a graph where every edge has 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$ edge-disjoint flows from vertex $1$ to vertex $i$ at the same time (that is, no edge belongs to two flows), then we say the maximum flow from vertex $1$ to vertex $i$ is $f_i$.

The first line 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. The graph is guaranteed to have no self-loops, but it may contain multiple edges. It is guaranteed to be a directed acyclic graph.

Output exactly one 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$, output its value; otherwise output $k$.

The graph in the first sample is shown below:  We can find $4$ edge-disjoint paths from vertex $1$ to vertex $7$: $\text{1->7}$ $\text{1->5->7}$ $\text{1->3->6->7}$ $\text{1->2->4->7}$ We cannot find any more edge-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$. Translated by ChatGPT 5