题目描述

题目译自 PA 2021 Runda 5 Fiolki 2

Byteasar 是一名化学家。你可能还记得，许多年前他因一项实验而闻名，该实验产生了一种特定的物质 X（你可以在这里阅读更多关于 Byteasar 的冒险故事）。由于上述物质根本没有解决人类的所有问题，这次他没有试图生产这种物质或找寻任何其他具体的解决方案——他只是在进行实验和评估其结果。

在 Byteasar 的实验室里有 $n$ 个样品瓶，用 $1$ 到 $n$ 的整数编号，这些样品瓶用 $m$ 根导管连接，物质可以从导管中流过。所有的样品瓶都处于两两不同的高度，液体只能通过导管往低处流。每根导管都有两端——第 $i$ 根导管的一端与编号为 $a_i$ 的样品瓶相连，另一端与编号为 $b_i$ 的样品瓶相连，我们知道编号 $a_i$ 的样品瓶比 $b_i$ 的样品瓶高。此外，每根导管都被一个导管夹夹住，以阻止物质的流动。Byteasar 可以在任何时候选择任何导管夹并打开它，让物质从样品瓶 $a_i$ 自由地流向样品瓶 $b_i$，在所有物质从一个样品瓶流向另一个样品瓶后，再夹住它。由于导管夹是机械式卡箍，保持其打开需要用力，因此在任何时候都只能打开一个导管夹。

编号为 $1$ 至 $k$ 的样品瓶含有危险化学品。这些样品瓶中的每一个都包含一种不同的物质。编号大于 $k$ 的样品瓶最初是空的。

化学品是非常危险的，在任何情况下都不允许不同的物质混合在一起——这种混合的后果可能是灾难性的。由于流动的物质会留下微小的沉淀物，所以甚至不能让一种物质倒入以前装有任何其他物质的样品瓶中。

Byteasar 唯一能做的就是在样品瓶之间移动这些物质，确保没有两个物质混合。这并不是毫无意义的——通过以安全的方式运输物质，他可以把这些物质移到其他样品瓶中，这样更方便他研究它们的特性。

Byteasar 现在想选择一个区间 $[l, r]$，其中满足 $k+1\le l\le r\le n$，并将尽可能多的物质转移到该区间的任何编号的样品瓶中，然后继续测试那些方便放置的化学品。由于他不能决定哪个区间对他来说是最方便的，对于每个可能的区间 $[l, r]$，他想知道他能最多将多少种不同的物质转移到编号在区间 $[l, r]$ 的样品瓶中。让我们用 $f(l, r)$ 来表示这个值。

帮助 Byteasar 写一个程序，根据他的实验室的描述，计算对于区间 $[0, k]$ 中的每个 $x$，有多少个区间 $[l,r]$ 满足 $f(l,r)=x$。

输入格式

第一行三个整数 $n,m,k\ (2\le n\le 10^5,1\le m\le 10^6,1\le k\le 50,k<n)$，分别表示样品瓶的数量，连接样品瓶的导管数量和最初装有 Byteasar 正在测试的物质的样品瓶数量。

接下来 $m$ 行，每行两个整数 $a_i,b_i\ (1\le a_i\le n,k+1\le b_i\le n)$，表示样品瓶 $a_i$ 和 $b_i$ 之间有导管，样品瓶 $a_i$ 中的物质可以转移到样品瓶 $b_i$ 中。

我们保证对实验室的描述是合法的，也就是说，不存在整数 $p\ge 2$，使得一个样品瓶的序列 $v_1, v_2, v_3,\ldots, v_p$ 满足 $v_1=v_p$ 且对于每个 $i\in [1,p-1]$ 都有样品瓶 $v_i$ 中的物质可以转移到样品瓶 $v_{i+1}$ 中。换句话说，如果我们把样品瓶当作一个图的顶点，把导管当作这个图的有向边，那么输入就描述了一个有向无环图。

请注意，输入中没有指出样品瓶所处的高度。然而，对于每一对由导管直接连接的样品瓶，可以知道哪一个样品瓶的位置更高。

输出格式

输出 $k+1$ 行。其中第 $i$ 行包含一个整数，表示满足 $k+1\le l\le r\le n$ 且 $f(l, r)=i-1$ 这样的区间 $[l, r]$ 的数量。

9 10 2
1 3
1 5
2 5
5 4
5 6
2 6
2 9
2 8
1 5
1 9

1
9
18