No.2418 Well-Informed! Nafmo-kun
タグ : / 解いたユーザー数 176
作問者 :
LaFolia13
hikikomori
sepa38
Seed57_cash
Problem Statement
There are $2N$ students in Nafmo's class, including Nafmo himself. They are assigned attendance numbers $1$ to $2N$.
During class, the teacher told them, "Form groups of $2$." The students disliked forming pairs with "people they do not know".
In the end, everyone formed pairs in such a way that the number of pairs of people who do not know each other was minimized.
The well-informed Nafmo has $M$ pieces of information: he knows that the people with attendance numbers $A_i$ and $B_i$ are acquainted.
Based on the M pieces of information Nafmo has, what is the maximum possible number of pairs of people who do not know each other?
Here, if $X$ and $Y$ are acquainted and $Y$ and $Z$ are acquainted, then $X$ and $Z$ are considered acquainted.
Constraints
- $1 \leq N \leq 10^5$
- $0 \leq M \leq 10^5$
- $1 \leq A_i, B_i \leq 2 \times N$
- If $i \neq j$, then $(A_i, B_i) \neq (A_j, B_j)$ and $(A_i, B_i) \neq (B_j, A_j)$
- $N$ pairs are always formed.
- All input values are integers.
Input
$N\ M$ $A_1 \ B_1$ $\ \vdots$ $A_M \ B_M$
Output
Output the number of pairs of people who do not know each other, followed by a newline.
Sample
Sample 1
Input
2 2 1 2 3 4
Output
0
By pairing person $1$ with person $2$ and person $3$ with person $4$, the number of pairs of people who do not know each other can be made zero.
Sample 2
Input
2 1 1 2
Output
1
Sample 3
Input
2 2 1 2 2 3
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。