問題一覧 > 通常問題

No.2286 Join Hands

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 34
作問者 : みここ / テスター : cureskol sapphire__15 👑 potato167
お気に入りにしたユーザー ProblemId : 9171 / 自分の提出
問題文最終更新日: 2023-04-28 08:19:39
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
yukicoder contest 386 (順位表) の他の問題:

Problem Statement

There are $N$ toddlers, and each toddler has two hands.

You make all the toddlers join hands by repeating the following procedure $N$ times.

  • Choose two toddlers who each still have a hand that is not joined.
  • Make the two chosen toddlers join their unjoined hands (if both of a toddler's hands are unjoined, either one may be used).

Note that in the end, no toddler is holding hands with themselves.

Now, there is a friendship list of toddlers consisting of $M$ pairs. The $i$-th pair in the list is $(u_i, v_i)$. If $(u, v)$ or $(v, u)$ is in the list, the $u$-th toddler and the $v$-th toddler are friends. Otherwise, the $u$-th toddler and the $v$-th toddler are not friends.

A toddler becomes happy when both hands are joined with friends, and becomes sad when both hands are joined with non-friends. A toddler with only one hand joined with a friend is neither happy nor sad.

Among all ways of joining hands, find the maximum value of $(\text{number of happy toddlers})-(\text{number of sad toddlers})$.

Input

$N \ M$
$u_1 \ v_1$
$\vdots$
$u_M \ v_M$
  • All input values are integers.
  • $2 \le N \le 5000$
  • $0 \le M \le 5000$
  • $1 \le u_i < v_i \le N$
  • If $i \neq j$, then $(u_i, v_i) \neq (u_j, v_j)$.

Output

Output the answer, followed by a newline.

Sample

Sample 1
Input
6 3
1 2
1 3
4 5
Output
2

By having them join hands in the following order, the number of happy toddlers can be made $3$ and the number of sad toddlers $1$.

  • Make $1$ and $2$ join hands.
  • Make $1$ and $3$ join hands.
  • Make $2$ and $6$ join hands.
  • Make $3$ and $6$ join hands.
  • Make $4$ and $5$ join hands.
  • Make $4$ and $5$ join hands.

Since the number of happy toddlers cannot be made greater than the number of sad toddlers by $3$ or more, the answer is $2$.

Sample 2
Input
3 1
1 2
Output
-1

Note that no toddler can be holding hands with themselves.

Sample 3
Input
3 0
Output
-3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。