← 返回题目列表

AtCoder · agc011_c

C. 平方图

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

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