408370: GYM103107 J JOJO's Factory

Aki is the prime minister in JOJO's Factory.

There are two types of machines in the factory, which are called A-machine and B-machine respectively. Both the number of two types of machines are $$$N$$$. One A-machine should work with exactly one B-machine and one B-machine should work with exactly one A-machine.

Unfortunately, some pairs of machines can not work together due to some unknown reason. A pair $$$(i,j)$$$ means $$$i$$$-th A-machine can not work with $$$j$$$-th B-machine.

In order to improve the efficiency, you, his staff, should find a plan that the most A-machines can run normally.

Luckily, Aki is a talented prime minister, so the number of un-working pairs is no more than $$$2N-3$$$.

The first line contains two integers $$$N, M ~ (5 \leq N \leq 5 \times 10^5; ~ 0 \leq M \leq 2N-3)$$$ denoting the count of machines and the count of pairs of machines that don't work together.

Then next $$$M$$$ lines follows, each containing two integers $$$i, j ~ (1 \leq i, j \leq N)$$$ denoting the un-working pairs. It is guaranteed that all pairs of $$$(i,j)$$$ are different.

Output one line containing the maximal number of normally running A-machines.

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

3