问题 28495 --「ZJOI2016」电阻网络

28495: 「ZJOI2016」电阻网络

时间限制: 1 Sec  内存限制: 256 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS0元][下载测试数据0元][7610kb]

题目描述

小 Y 是一个充满智慧的女孩子,但是她只会使用串并联的方法计算两个节点之间的电阻。

现在小 Y 有一个电阻网络,问有多少点对 u,v (u≠v)u, v \ (u \neq v)u,v (uv) 之间的电阻可以用串并联的方法计算出来。

我们来形式化地定义一下点对 u,v (u≠v)u, v \ (u \neq v)u,v (uv) 之间的电阻能用串并联的方法计算出来的条件。首先我们把电阻网络看成一个 nnn 个点 mmm 条边的图(每个电阻对应一条边)。令 SSS 表示从 uuuvvv 的所有简单路径(不经过重复的点的路径)上点的并集,也就是对于一个点 xxx,如果存在一条从 uuuvvv 的简单路径经过这个点,那么它就在集合 SSS 中。如果 SSS 非空且 SSS 的导出子图是 u,vu,vu,v 为端点的二端串并联图,那么 u,vu,vu,v 之间的电阻就能用串并联方法计算。

  1. 一个有两个不同端点 s,ts,ts,t 的图被称为二端图,其中一个称为源点,另一个称为汇点。

  2. 两个二端图 X,YX,YX,Y 并联 (parallel composition) 是指建一个新图,把 XXXYYY 的源点和汇点分别合并起来。

  3. 两个二端图 X,YX,YX,Y 串联 (series composition) 是指建一个新图,把 XXX 的汇点和 YYY 的源点合并起来。

  4. 由若干个两个点一条边的二端图经过一系列串并联变化之后形成的图称为二端串并联图。

集合 SSS 的导出子图点集为 SSS,边集由原图中两个端点都在 SSS 中的边构成。

输入

第一行包含两个正整数 n,mn,mn,m,表示电阻网络中的节点数和电阻数。

接下来 mmm 行,每行包含两个正整数 u,v (1≤u,v≤n, u≠v)u,v \ (1 \leq u,v \leq n, \ u \neq v)u,v (1u,vn, uv),表示有一个电阻在节点 uuuvvv 之间。

输出

输出共一行,表示答案,即有多少点对之间的电阻可以使用串并联的方法计算出来。

样例输入

6 6
1 2
1 3
1 4
2 3
2 4
5 6

样例输出

6

提示




对于所有的数据,n,m≤105n,m \leq 10^5n,m105



来源

[提交][状态]