Safe Chemical Transportation

Byteasar is a chemist known for his famous experiment producing a special substance X. This time, however, he is not trying to produce any specific substance, but merely transferring dangerous chemicals among sample bottles in his laboratory.

There are n sample bottles numbered from 1 to n. They are arranged in order of strictly decreasing height, so bottle 1 is the highest and bottle n is the lowest. The bottles are connected by m tubes. Each tube i connects bottle a_i and bottle b_i (with 1 ≤ a_i < b_i ≤ n) so that the fluid can only flow from bottle a_i (the higher one) to bottle b_i (the lower one) when its clamp is opened. At any moment only one tube’s clamp can be opened. After opening, ALL the material available flows from the higher bottle to the lower bottle; then the clamp is closed.

Bottles 1 to k each initially contain a dangerous chemical (all different), and bottles k+1 through n are initially empty. The chemicals are extremely dangerous – under no circumstance should two different chemicals ever mix (even a trace of residue from a different chemical prohibits any transfer into that bottle later).

Using the tubes, Byteasar can transfer a chemical from one bottle to another provided the destination bottle is completely clean (i.e. it has never contained any chemical different from the one that is being transferred). In this way, he can safely move chemicals from their starting bottles. In particular, he wants to select an interval of bottles with indices in the range [l, r] (with k+1 ≤ l ≤ r ≤ n) as a convenient storage for chemicals, and then try to transfer as many as possible of the chemicals (initially in bottles 1 to k) into the bottles whose indices lie in the chosen interval.

Let \(f(l,r)\) be the maximum number of chemicals that can be transferred into bottles in the interval \([l,r]\) via a sequence of transfers as described, under the constraint that no bottle ever carries more than one chemical (or a chemical different from an earlier one). Equivalently, if we view a transfer from an initial bottle (a source from 1 to k) to a bottle in \([l, r]\) as the existence of a path in the directed acyclic graph (DAG) described by the bottles and tubes, and since the transfers must not "mix" by sharing a bottle, \(f(l,r)\) is the size of a maximum set of vertex-disjoint paths from some of the sources \(\{1,2,\dots,k\}\) to some of the target bottles in \(\{l,l+1,\dots,n\}\>.

Byteasar is not sure which interval is most convenient for him. For every possible interval \([l,r]\) with k+1 ≤ l ≤ r ≤ n, he wants to know the value of \(f(l,r)\). Your task is to compute, for every \(x\) between 0 and k (inclusive), how many intervals \([l,r]\) satisfy \(f(l,r)=x\).

Input Format

The first line contains three integers \(n, m, k\) (with \(1 \leq k < n\)). Each of the next \(m\) lines contains two integers \(a_i\) and \(b_i\) denoting that there is a tube connecting bottle \(a_i\) and bottle \(b_i\) (with \(a_i < b_i\)).

Output Format

Output k+1 space-separated integers. The \(x\textsuperscript{th}\) number (for \(x=0,1,\dots,k\)) should be the number of intervals \([l,r]\) (with \(k+1 \leq l \leq r \leq n\)) for which \(f(l,r)=x\).

Note

Any formulas that appear in the statement are represented in LaTeX format. In particular, the formula for \(f(l, r)\) is given as:

[ f(l,r) = \text{maximum number of vertex-disjoint paths from } {1,2,\dots,k} \text{ to } {l, l+1,\dots,n}. ]

</p>

inputFormat

The first line contains three integers \(n, m, k\). Each of the next \(m\) lines contains two integers \(a_i, b_i\) (\(1 \le a_i < b_i \le n\)).

outputFormat

Output exactly \(k+1\) space‐separated integers. The \(x\)th integer (for \(x=0,1,\dots,k\)) indicates the number of intervals \([l,r]\) (with \(k+1 \leq l \leq r \leq n\)) satisfying \(f(l,r)=x\).

sample

5 4 1
1 3
1 4
3 5
4 5

1 9