#P0370. 神秘的法阵

神秘的法阵

题目描述

恭喜你天选之子,你穿越到了算法的世界,你发现这个世界的土著正在进行一个神秘的仪式。

他们在计算开启穿越之门的密码,这时候你从天而降,他们想请你帮忙看看这个问题。

问题画在一个沙地上,上面写着给你 nn 个点(编号从 11nn)和 mm 条边,保证无重边自环,这 mm 条边将会构成一个法阵,这个所谓的法阵就是算法中的图。

但是你一眼就发现这个图是残破不全的,开启穿越之门的密码就是你需要找到你应该补全多少条边才可以使得阵法齐全。

这里需要补充的边的条件如下:如果 xx 可以到达 yyyy 可以到达 zz,但是 xxzz 却不存在边,那么你需要将 xxzz 的这条边补全。

问题便是询问你,你应该补全多少条边?

样例输入

第一行两个整数 nnmm

接下来输入 mm 行,每行两个整数 u, vu,\ v,代表 uuvv 之间有一条边链接。

样例输出

输出你需要补全的边数。

样例

4 3
1 2
2 3
1 4
3

样例解释:

1231 - 2 - 3,所以 1133 需要补充一条边。

32143 - 2 - 1 - 4,所以 3344 需要补充一条边。

2142 - 1 - 4,所以 2244 需要补充一条边。

数据范围

2n2×1052 \le n \le 2 \times 10^{5}

0m2×1050 \le m \le 2 \times 10^{5}

1u<vn1 \le u < v \le n