该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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 be 3 4 or 114514 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