問題一覧 > 通常問題

No.3694 Sworn Enemies

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 37
作問者 : yuki2006
お気に入りにしたユーザー ProblemId : 9953 / 自分の提出
問題文最終更新日: 2026-09-09 17:26:23
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
チーム機能テストコンテスト (順位表) の他の問題:

Problem Statement

There are $N$ participants, and the $i$-th participant is called participant $i$. Among them, $M$ pairs are on bad terms and cannot be placed on the same team.

Determine whether all participants can be divided into exactly $2$ teams. Note that either team may be empty.

Input

$N\ M$
$a_1\ b_1$
$\vdots$
$a_M\ b_M$
  • $2 \le N \le 2 \times 10^5$
  • $0 \le M \le 2 \times 10^5$
  • $1 \le a_i \lt b_i \le N$
  • The same pair is not given $2$ or more times
  • All input values are integers

Output

Print Yes if the division is possible, and No otherwise. Print a newline at the end.

Sample

Sample 1
Input
4 3
1 2
2 3
3 4
Output
Yes

If we divide them into participants $1, 3$ and participants $2, 4$, every pair on bad terms ends up on different teams.

Sample 2
Input
3 3
1 2
2 3
1 3
Output
No

Since the $3$ participants are all on bad terms with one another, they cannot be divided into $2$ teams.

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