题目描述

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

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 < l \leq r \leq n$，然后他会将尽可能多的物质转移到该区间的任何编号的样品瓶中并继续测试那些方便放置的化学品。由于他不能决定哪个区间对他来说是最方便的，对于每个可能的区间 $[l, r]$，他想知道他能最多将多少种不同的物质转移到编号在区间 $[l, r]$ 的样品瓶中。我们用 $f(l, r)$ 来表示这个值。

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

输入格式

第一行，三个整数 $n, m, k$，表示样品瓶的数量、连接样品瓶的导管数量和最初装有 Byteasar 正在测试的物质的样品瓶数量。

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

我们保证对实验室的描述是合法的，即如果我们把样品瓶当作一个图的顶点，把导管当作这个图的有向边，那么输入就描述了一个有向无环图。

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

输出格式

$k + 1$ 行，其中第 $i$ 行包含一个整数，表示满足 $k < l \leq r \leq 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

提示

对于 $100\%$ 的数据，$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$。