Vials 2

Bajtazar is a chemist. Years ago he became known for an experiment that produced substance X. That substance did not solve all of humanity's problems, so this time he does not try to make it or any other particular solution. He simply experiments and evaluates the results.

Bajtazar's lab has $n$ vials numbered from 1 to $n$, connected by $m$ tubes through which substances can flow. All vials are at pairwise different heights. Liquid in each tube can flow only downward. Each tube connects vial $a_i$ to vial $b_i$, where vial $a_i$ is higher than vial $b_i$. Each tube is pinched by a clamp that blocks the flow. At any moment Bajtazar can choose a clamp and open it, letting substance flow from $a_i$ to $b_i$. Once all substance has flowed from one vial to the other, he closes the clamp again. Clamps are mechanical and holding one open takes effort, so at most one clamp can be open at any moment.

Vials $1$ to $k$ contain dangerous chemicals, each a different substance. Vials numbered greater than $k$ start empty.

The chemicals are extremely dangerous, and under no circumstances may different substances mix. Substances leave a microscopic residue, so a substance may not flow into a vial that previously held any other substance.

Bajtazar can only move substances between vials, making sure that no two of them mix. Moving them safely is useful, because he can carry each substance to a vial where it is more convenient to study.

The chemist wants to choose an interval $[\ell, r]$ with $k + 1 \le \ell \le r \le n$, move as many liquids as possible into vials in that interval, and study the chemicals placed there. He cannot decide which interval is best, so for every interval $[\ell, r]$ he wants to know the maximum number of different liquids $f(\ell, r)$ that can be moved into vials numbered in $[\ell, r]$. Write a program that, for each $x$ in $[0, k]$, counts the intervals $[\ell, r]$ with $f(\ell, r) = x$.

The first line contains three integers $n$, $m$, $k$ ($2 \le n \le 10^5$; $1 \le m \le 10^6$; $1 \le k \le 50$; $k < n$), the number of vials, the number of tubes, and the number of vials that initially hold substances.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n$; $k + 1 \le b_i \le n$), meaning liquid can flow directly from vial $a_i$ to vial $b_i$ through a tube.

The lab description is valid. The directed graph with vials as vertices and tubes as edges has no cycles. Heights are not given, but for every pair of vials joined by a tube, it is known which vial is higher.

Print $k + 1$ lines. The $i$-th line contains one integer: the number of intervals $[\ell, r]$ with $k + 1 \le \ell \le r \le n$ and $f(\ell, r) = i - 1$.

No tube leads into vial 7, so $f(7, 7) = 0$.

Bajtazar can move only one substance into each of the intervals $[3, 3]$, $[4, 4]$, $[5, 5]$, $[6, 6]$, $[8, 8]$, $[9, 9]$, $[4, 5]$, $[6, 7]$, and $[7, 8]$, so $f$ equals 1 for each of them. For $[3, 3]$ the substance must come from vial 1, and it ends up in vial 3. For $[7, 8]$ and $[8, 8]$ it must be the substance from vial 2.

Suppose both substances are moved into $[4, 5]$. The substance poured into vial 4 has to pass through vial 5 and leave a residue there, which makes it impossible to bring the second substance into vial 5. For every other interval, Bajtazar can move both substances.