The LSZC Tokens
测试数据来自 AOCode/1043
P1043 The LSZC Tokens
Problem Background
The union of LSZC is a team that was set up by LCW. Now it's leader is WBW(2022.4.29). But Cui2010 gets into the Union somehow. He's even an admin! Now AppOfficer and Cui2010 is competing with each other for the LSZC tokens. Without doubt, AppOfficer does much better than Cui2010 as an admin. So everyone will absolutely vote him. But Cui2010 doesn't want to lose.
Problem Statement
There are \(n\) people in the union of LSZC(n is an odd number). Now Cui2010 is going to persuade some of the members to vote him. However, some of the people in the union have no minds their own. There are \(m\) kinds of that relationship.
For example:
- \(x\ y\) means that if \(x\) agrees to vote Cui2010, \(y\) will vote him too.
- But if \(y\) agrees to vote him, \(x\) will stay disagreed.
- Note that there won't be two people that can make one person agrees. For example, if
2 4
exists, there won't be3 4
or114514 4
and stuff. - Note that there won't be circles. For example, there won't be
x y
,y z
,z x
.
If Cui2010 gets more than half of the votes, he'll win. Now Cui2010 wants to now how many people at least he needs to persuade to make sure that he can win the competition.
Input
First line includes two integers \(n\) and \(m\).
Next \(m\) lines, every line contains two integers \(x\) and \(y\).
Output
One integer which means how many people Cui2010 need to persuade.
Constraints
- \( 2 \le n \le 10^5 \)
- \(n\) is an odd number.
- \( 1 \le m \le n-1\)
- \( 1 \le x,y \le n\)
Samples
Input 1
5 2
3 1
4 3
Output 1
1
It's easy to see that he only needs to persuade 4
.
Input 2
9 4
3 1
8 9
2 5
6 7
Output 2
3
信息
- ID
- 1004
- 难度
- 1000
- 分类
- (无)
- 标签
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者
相关
在下列比赛中: