← 返回题目列表

AtCoder · agc006_f

F. 停电

中文机器翻译题面 查看原题

分数: 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

白色单元格不能涂成黑色。