我们有一个 \(N\) 行 \(N\) 列的矩阵。第 \(i\) 行第 \(j\) 列的格子表示为 \((i,j)\)。
开始时，有 \(M\) 个格子是黑色，其他格子都是白色。特别地，开始时格子 \((a_1,b_1),(a_2,b_2),\cdots,(a_M,b_M)\) 是黑色。
スヌケ君会按照以下的规则尽可能多的将白色格子涂成黑色：
- 对于整数 \(1\le x,y,z\le N\)，如果 \((x,y)\) 和 \((y,z)\) 都是黑色，那么就把 \((z,x)\) 涂黑。
请计算出当再也没有白色格子能被涂黑时，黑色格子的个数。
\(1\le N,M\le 10^5;1\le a_i,b_i\le N\)。1
题解
按照套路，我们应该把行和列看成点，即有 \(1\sim N\) 个点，每个格子 \((x,y)\) 可以看成是 \(x\to y\) 的一条有向边。如果存在边 \((x,y)\) 与边 \((y,z)\)，就连边 \((z,x)\)，询问最终有几条边。
我们将每个弱连通分量分开考虑。
我们考虑什么时候不能加边了，大概是这 \(2\) 中情况：
- 已经是完全图了，边数为 \(n\times (n - 1)\)。
- 图被划分为 \(3\) 个集合（可以是空集）\(A,B,C\)，\(A\) 的所有点向 \(B\) 的所有点连边，\(B\) 的所有点向 \(C\) 连边，\(C\) 的所有点向 \(A\) 连边，边数为 \(|A|\times |B| + |B|\times |C| + |C|\times |A|\)。
我们发现一个点集如果会到情况 \(2\)，那就到情况 \(2\)，否则就是情况 \(1\)。
于是我们尝试划分集合，将弱连通块中每个点一遍 dfs 染色，如果染色成功，那就是情况 \(2\)，否则就是情况 \(1\)。