# #675. 【NOI2021】庆典

C 国是一个繁荣昌盛的国家，它由 $n$ 座城市和 $m$ 条有向道路组成，城市从 $1$ 到 $n$ 编号。如果从 $x$ 号城市出发，经过若干条道路后能到达 $y$ 号城市，那么我们称 $x$ 号城市可到达 $y$ 号城市，记作 $x \Rightarrow y$。C 国的道路有一个特点：对于三座城市 $x,~y,~z$，若 $x \Rightarrow z$ 且 $y \Rightarrow z$，那么有 $x \Rightarrow y$ 或 $y \Rightarrow x$。

### 样例一

#### input

5 6 4 1
1 2
1 3
1 4
2 5
4 5
5 4
1 4 5 1
2 3 5 3
1 2 5 2
3 4 5 1



#### output

4
4
4
0



### 测试点约束

$1 \sim 4$ $5$ $=0$
$5 \sim 7$ $1000$ $\le 2$
$8 \sim 9$ $3\times 10^5$ $=0$ $m=n-1$
$10 \sim 11$ $3\times 10^5$ $=1$ $m=n-1$
$12 \sim 14$ $3\times 10^5$ $=2$ $m=n-1$
$15 \sim 16$ $3\times 10^5$ $=0$
$17 \sim 19$ $3\times 10^5$ $=1$
$20 \sim 25$ $3\times 10^5$ $=2$