分数: 800 点
问题陈述
Takahashi 收到了一张无向图 N 顶点,编号 1, 2, ..., N。 该图中的边由下式表示 (u_i, v_i)。 该图中不存在自环和重边。
基于该图,高桥现在正在构建一个新图 N^2 顶点,其中每个顶点都用一对整数标记 (a, b) (1 \leq a \leq N, 1 \leq b \leq N)。 这个新图中的边是通过以下规则生成的:
- 跨越顶点之间的边 (a, b) 和 (a', b') 当且仅当原始图中存在以下两条边:顶点之间的边 a 和 a',以及顶点之间的边 b 和 b'.
这个新图中有多少个连通分量?
约束
- 2 \leq N \leq 100,000
- 0 \leq M \leq 200,000
- 1 \leq u_i < v_i \leq N
- 不存在一对不同的整数 i 和 j 这样 u_i = u_j 和 v_i = v_j.
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 u_2 v_2 : u_M v_M
输出
打印 Takahashi 构建的图中连通分量的数量。
示例输入 1
3 1 1 2
示例输出 1
7
高桥构建的图表如下。

示例输入 2
7 5 1 2 3 4 3 5 4 5 2 6
示例输出 2
18