#BZOJ4238. 电压
-
ID: 2831
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
电压
No submission language available for this problem.
题目描述
你知道Just Odd Inventions社吗？这个公司的业务是“只不过是奇妙的发明(Just Odd Inventions)”。这里简称为JOI社。
JOI社的某个实验室中有着复杂的电路。电路由n个节点和m根细长的电阻组成。节点被标号为1~N
每个节点有一个可设定的状态【高电压】或者【低电压】。每个电阻连接两个节点，只有一端是高电压，另一端是低电压的电阻才会有电流流过。两端都是高电压或者低电压的电阻不会有电流流过。
某天，JOI社为了维护电路，选择了一根电阻，为了能让【只有这根电阻上的电流停止流动，其他M-1根电阻中都有电流流过】，需要调节各节点的电压。为了满足这个条件，能选择的电阻共有多少根？
对了，JOI社这个奇妙的电路是用在什么样的发明上的呢？这是公司内的最高机密，除了社长以外谁都不知道哦~
现在给出电路的信息，请你输出电路维护时可以选择使其不流的电阻的个数。
输入格式
第一行两个空格分隔的正整数N和M，表示电路中有N个节点和M根电阻。
接下来M行，第i行有两个空格分隔的正整数Ai和Bi(1<=Ai<=N,1<=Bi<=N,Ai≠Bi)，表示第i个电阻连接节点Ai和节点Bi。
输出格式
输出一行一个整数，代表电路维护时可选择的使其不流的电阻个数。
4 4
1 2
2 3
3 2
4 3
2
数据范围与约定
可以选择第一根电阻或第四根电阻。
2<=N<=10^5
1<=M<=2*10^5
不保证图是连通的，不保证没有重边