分数: 1700 点
问题陈述
我们有一个网格 N 行和 N 列。 牢房位于 i第行和 j- 第列表示 (i, j).
最初, M 的单元格涂成黑色,所有其他单元格涂成白色。 具体来说,细胞(a_1, b_1), (a_2, b_2), ..., (a_M, b_M) 被漆成黑色。
Snuke 将根据以下规则尝试将尽可能多的白细胞涂成黑色:
- 如果两个单元格 (x, y) 和 (y, z) 都是黑色和单元格 (z, x) 对于整数来说是白色的 1≤x,y,z≤N,绘制单元格(z, x)黑色。
求当没有更多的白色单元格可以被涂成黑色时黑色单元格的数量。
约束
- 1≤N≤10^5
- 1≤M≤10^5
- 1≤a_i,b_i≤N
- 所有对 (a_i, b_i) 是不同的。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 a_2 b_2 : a_M b_M
输出
当没有更多的白色单元格可以涂成黑色时,打印黑色单元格的数量。
示例输入 1
3 2 1 2 2 3
示例输出 1
3
可以将一个白色单元格涂成黑色,如下所示:
- 由于细胞(1, 2) 和 (2, 3) 都是黑色和单元格 (3, 1)是白色的,绘制单元格(3, 1)黑色。
示例输入 2
2 2 1 1 1 2
示例输出 2
4
可以将两个白色单元格涂成黑色,如下所示:
- 由于细胞(1, 1) 和 (1, 2) 都是黑色和单元格 (2, 1)是白色的,绘制单元格(2, 1)黑色。
- 由于细胞(2, 1) 和 (1, 2) 都是黑色和单元格 (2, 2)是白色的,绘制单元格(2, 2)黑色。
示例输入 3
4 3 1 2 1 3 4 4
示例输出 3
3
白色单元格不能涂成黑色。