시험관 2

바이타자르는 화학자이다. 여러 해 전 그는 물질 X를 만든 실험으로 이름을 알렸다. 그 물질이 인류의 문제를 모두 해결하지는 못했으므로, 이번에는 그 물질이나 다른 특정 용액을 만들려 하지 않는다. 그는 그저 실험을 하고 결과를 평가한다.

바이타자르의 실험실에는 1부터 $n$까지 번호가 붙은 시험관 $n$개가 있고, 액체가 흐를 수 있는 관 $m$개로 연결되어 있다. 모든 시험관은 서로 다른 높이에 있다. 각 관의 액체는 아래 방향으로만 흐른다. $i$번째 관은 시험관 $a_i$와 시험관 $b_i$를 잇고, 시험관 $a_i$가 시험관 $b_i$보다 높이 있다. 각 관에는 흐름을 막는 집게가 달려 있다. 바이타자르는 언제든 집게 하나를 골라 열 수 있고, 그러면 물질이 $a_i$에서 $b_i$로 흐른다. 물질이 모두 옮겨지면 집게를 다시 닫는다. 집게는 기계식이라 열린 상태를 유지하려면 힘이 들므로, 동시에 열려 있을 수 있는 집게는 하나뿐이다.

1번부터 $k$번까지 시험관에는 위험한 화학 물질이 들어 있으며, 각 시험관마다 서로 다른 물질이 하나씩 있다. $k$보다 큰 번호의 시험관은 처음에 비어 있다.

이 화학 물질은 매우 위험해서 어떤 경우에도 서로 다른 물질이 섞이면 안 된다. 물질은 미세한 찌꺼기를 남기므로, 이전에 다른 물질이 들어 있었던 시험관으로 물질을 흘려보내는 것도 허용되지 않는다.

바이타자르가 할 수 있는 일은 시험관 사이에서 물질을 옮기는 것뿐이며, 이때 어떤 두 물질도 섞이지 않도록 해야 한다. 물질을 안전하게 옮길 수 있으면 성질을 조사하기 편한 시험관으로 옮겨 둘 수도 있다.

화학자는 이제 $k + 1 \le \ell \le r \le n$을 만족하는 구간 $[\ell, r]$을 고르고, 그 구간에 속한 시험관으로 액체를 가능한 한 많이 옮긴 뒤 그곳에 놓인 화학 물질을 조사하려 한다. 어느 구간이 가장 편리한지 정하지 못했으므로, 각 구간 $[\ell, r]$에 대해 구간 안의 시험관으로 옮길 수 있는 서로 다른 액체의 최대 개수 $f(\ell, r)$을 구하려 한다. 각 $x \in [0, k]$에 대해 $f(\ell, r) = x$인 구간 $[\ell, r]$의 개수를 세는 프로그램을 작성하라.

첫 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($2 \le n \le 10^5$; $1 \le m \le 10^6$; $1 \le k \le 50$; $k < n$). 각각 시험관의 수, 관의 수, 처음에 물질이 들어 있는 시험관의 수이다.

다음 $m$개의 줄에는 정수 $a_i$, $b_i$ ($1 \le a_i \le n$; $k + 1 \le b_i \le n$)가 주어진다. 이는 시험관 $a_i$에서 시험관 $b_i$로 관을 따라 액체가 바로 흐를 수 있다는 뜻이다.

실험실 설명은 올바르다. 시험관을 정점, 관을 간선으로 보면 그래프에 순환이 없다. 높이는 주어지지 않지만, 관으로 직접 연결된 각 쌍에 대해서는 어느 시험관이 더 높은지 알 수 있다.

$k + 1$개의 줄을 출력한다. $i$번째 줄에는 $k + 1 \le \ell \le r \le n$이고 $f(\ell, r) = i - 1$인 구간 $[\ell, r]$의 개수를 한 정수로 쓴다.

7번 시험관으로 가는 관이 없으므로 $f(7, 7) = 0$이다.

바이타자르는 구간 $[3, 3]$, $[4, 4]$, $[5, 5]$, $[6, 6]$, $[8, 8]$, $[9, 9]$, $[4, 5]$, $[6, 7]$, $[7, 8]$에 각각 하나의 물질만 옮길 수 있으므로, 이 구간들의 $f$는 모두 1이다. $[3, 3]$에는 1번 시험관의 물질이 들어가 3번 시험관에 놓인다. $[7, 8]$과 $[8, 8]$에는 2번 시험관의 물질이어야 한다.

두 물질을 모두 $[4, 5]$로 옮기려 하면, 4번 시험관에 부은 물질이 5번 시험관을 지나면서 찌꺼기를 남기고, 그 결과 두 번째 물질을 5번 시험관에 넣을 수 없다. 나머지 구간에서는 두 물질을 모두 옮길 수 있다.