Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Description

There are $n$ people, each with two attributes: combat power and stamina.

The coach of these $n$ people is going to train them, and each training session involves two people $(a, b)$. One of the following training methods will be chosen:

• Person $a$ practices swordsmanship, increasing their combat power by 1, while person $b$ watches from the side, increasing their stamina by 1;
• Person $b$ practices swordsmanship, increasing their combat power by 1, while person $a$ watches from the side, increasing their stamina by 1.

Currently, $m$ pairs of people have been scheduled for training, and you get to decide the training method for each pair.

The coach wants every person's combat power and stamina to be even numbers. Your task is to find the minimum number of additional training sessions required.

Input Format

The first line contains two integers $n$ and $m$. The next $m$ lines each contain two integers, representing the two people $(x, y)$ for each scheduled training session.

Output Format

Output a single integer, representing the minimum number of additional training sessions needed.

Samples

3 4
1 2
2 3
1 1
3 3

2

Sample Explanation

For convenience, a pair $(x, y)$ denotes that person $x$'s combat power increases by 1 and person $y$'s stamina increases by 1.

After the initial scheduled training sessions $(1,2),(3,2),(1,1),(3,3)$, the stamina and combat power of each person are as follows:

After conducting additional training sessions $(2,1)$ and $(2,3)$, the stamina and combat power of each person become:

Data Range

For 100% of the data: $1\le n,m\le 10^5$, $1\le x,y\le n$.