P9041 [PA 2021] Fiolki 2

Byteasar is a chemist. You may remember that many years ago he became famous because of an experiment that produced a certain substance $X$. Since that substance did not solve all of humanity’s problems at all, this time he is not trying to produce it or to find any other specific solution—he is simply conducting experiments and evaluating their results. In Byteasar’s laboratory there are $n$ flasks, numbered with integers from $1$ to $n$. They are connected by $m$ pipes through which substances can flow. All flasks are at pairwise different heights, and liquid can flow through a pipe only downwards. Each pipe has two ends: for the $i$-th pipe, one end is connected to flask $a_i$ and the other to flask $b_i$, and we know that flask $a_i$ is higher than flask $b_i$. Moreover, each pipe is clamped to block the flow. At any moment, Byteasar can choose any clamp and open it, allowing the substance to flow freely from flask $a_i$ to flask $b_i$, and after all substance has flowed from one flask to the other, clamp it again. Since the clamps are mechanical and keeping one open requires effort, at any time he can open at most one clamp. Flasks numbered from $1$ to $k$ contain dangerous chemicals. Each of these flasks contains a different substance. Flasks with numbers greater than $k$ are initially empty. The chemicals are extremely dangerous, and under no circumstances is it allowed to mix different substances—such mixing could have disastrous consequences. Because flowing substances leave tiny deposits, it is not even allowed to pour one substance into a flask that previously contained any other substance. The only thing Byteasar can do is move these substances between flasks while ensuring that no two substances ever mix. This is not pointless—by transporting the substances safely, he can move them into other flasks, which makes it easier for him to study their properties. Byteasar now wants to choose an interval $[l, r]$ with $k < l \leq r \leq n$. Then he will transfer as many substances as possible into flasks whose numbers lie in this interval $[l, r]$, and continue testing the chemicals placed conveniently. Since he cannot decide which interval is the most convenient for him, for every possible interval $[l, r]$ he wants to know the maximum number of different substances he can transfer into flasks with numbers in $[l, r]$. Let this value be denoted by $f(l, r)$. Help Byteasar write a program that, according to the description above, computes for each $x$ in the interval $[0, k]$ how many intervals $[l, r]$ satisfy $f(l, r) = x$.

The first line contains three integers $n, m, k$, denoting the number of flasks, the number of pipes connecting the flasks, and the number of flasks that initially contain the substances Byteasar is testing. The next $m$ lines each contain two integers $a_i, b_i$, meaning there is a pipe between flasks $a_i$ and $b_i, and the substance in flask $a_i$ can be transferred to flask $b_i$. We guarantee that the laboratory description is valid: if we treat flasks as vertices of a graph and pipes as directed edges, then the input describes a **directed acyclic graph**. Note that the input does not explicitly give the heights of the flasks. However, for each pair of flasks directly connected by a pipe, we know which flask is higher.

Output $k + 1$ lines. The $i$-th line contains one integer: the number of intervals $[l, r]$ such that $k < l \leq r \leq n$ and $f(l, r) = i - 1$.

For $100\%$ of the testdata, $2 \leq n \leq 10^5$, $1 \leq m \leq 10^6$, $1 \leq k \leq \min(n - 1, 50)$, $1 \leq a_i \leq n$, $k < b_i \leq n$. Translated by ChatGPT 5