连锁反应

题目描述

有一张 $n \times n$ 的网格，其中第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。

一开始共有 $m$ 个格子被涂成黑色，第 $i$ 个黑色的格子为 $(a_i, b_i)$（$\forall i \ne j, a_i \ne a_j$ 或 $b_i \ne b_j$）；其它所有格子都是白色的。

如果存在三个正整数 $x, y, z$（$1 \le x, y, z \le n$），满足 $(x, y)$ 和 $(y, z)$ 都是黑色的，那么你就可以将 $(z, x)$ 涂成黑色。

请求出你最多能使棋盘上有多少个黑色的格子。

输入格式

输入的第一行包含两个正整数 $n, m$，分别表示网格的大小以及初始黑色格子的数量。 接下来 $m$ 行，每行两个正整数 $a_i, b_i$，表示一个初始为黑的格子。

输出格式

输出一个正整数，表示最多能使棋盘上有多少个黑色的格子。

数据范围

对于 40% 的数据，$1 \le n \le 500, 1 \le m \le 4000$； 对于 100% 的数据，$1 \le n \le 10^5, 1 \le m \le 10^5$。

样例输入

2 2
1 1
1 2

样例输出

4

说明：先用 (1,1),(1,2) 涂黑 (2,1)；再用 (2,1),(1,2) 涂黑 (2,2)。此时共有 4 个点被涂黑。

知识点与难度

本题涉及的知识点从属于 GESP七级（图论、连通分量），难度等级：⭐⭐⭐⭐。

测试点分布