問題一覧 > 通常問題

No.2418 Well-Informed! Nafmo-kun

レベル : / AI推定難易度 : 575 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 176
作問者 : Nafmo2 / テスター : LaFolia13 dyktr_06 hikikomori sepa38 Seed57_cash Udon ryota2357
お気に入りにしたユーザー ProblemId : 9684 / 自分の提出
問題文最終更新日: 2023-08-12 16:02:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 016 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。