UVA12167 Proving Equivalences

在数学中，我们常常需要完成若干命题的等价性证明。 例如：有 $4$ 个命题 $a,b,c,d$，要证明他们是等价的，我们需要证明 $a\Leftrightarrow b$，然后 $b\Leftrightarrow c$，最后 $c\Leftrightarrow d$。注意每次证明是双向的，因此一共完成了 $6$ 次推导。另一种证明方法是：证明 $a\rightarrow b$，然后 $b\rightarrow c$，接着 $c\rightarrow d$，最后 $d\rightarrow a$，只须 $4$ 次证明。 现在我有 $n$ 个命题，并且我已经完成了 $m$ 条等价关系的证明，请你帮我求出至少还需要证明多少条等价关系才能使所有命题都满足与其他命题等价。 $1 \le n\le 2\times 10^4,0\le m \le 5 \times 10^4,1\le T\le 100$。

有 $T(T\le 100)$ 组数据，每组数据第一行为两个整数 $n$ 和 $m(1\le n\le 20000,0\le m\le 50000)$，即命题数和已完成的推导个数（编号为 $1\dots n$）。接下来 $m$ 行每行包含两个整数 $s1$ 和 $s2（1\le s1,s2\le n,s1\not =s2)$，表明已经证明了 $s1\rightarrow s2$。

输出还需要的等价关系的最小数量。

感谢 @[hicc0305](https://www.luogu.com.cn/user/21874) 提供的翻译 由 @[yinbe](https://www.luogu.com.cn/user/759152) 修缮