問題一覧 > 通常問題

No.1610 She Loves Me, She Loves Me Not, ...

レベル : / AI推定難易度 : 950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 160
作問者 : ygussany / テスター : tatyam kanra824
お気に入りにしたユーザー ProblemId : 6382 / 自分の提出
問題文最終更新日: 2021-07-21 18:19:57
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 305 (順位表) の他の問題:

Problem Statement

F.F. likes flower-petal fortune-telling. Having grown tired of the ordinary version, F.F. decided to do the fortune-telling with a graph. Specifically, the following operation is repeated as long as possible.

Operation: Choose any $1$ vertex to which exactly $1$ edge is incident, and remove it from the graph together with the incident edge.

After looking at the graph, F.F. found it too bothersome to actually do the fortune-telling. Given the graph that F.F. saw, tell F.F. whether the result of the fortune-telling can be made Yes. Here, the result of the fortune-telling being Yes means that the operation becomes impossible immediately after the above operation has been performed an odd number of times.

Input

$N\ \ M$
$A_1\ \ B_1$
$A_2\ \ B_2$
$\hspace{5mm} \vdots$
$A_M\ \ B_M$

  • $1 \le N \le 5000$
  • $0 \le M \le 5000$
  • $1 \le A_i, B_i \le N,\ A_i \neq B_i \ \ (1 \le i \le M)$
  • $\{A_i, B_i\} \neq \{A_j, B_j\} \ \ (1 \le i < j \le M)$
  • All input values are integers.
  • The given graph is a simple undirected graph. That is, edges have no direction, and the graph has no self-loops or parallel edges.
  • The vertices are numbered $1, 2, \dots, N$.
  • The edges are numbered $1, 2, \dots, M$.
  • Edge $i$ connects vertex $A_i$ and vertex $B_i$.

Output

If there exists a sequence of operations such that the operation becomes impossible immediately after an odd-numbered operation is performed, print Yes; otherwise, print No.

Sample

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

Initially, the numbers of edges incident to the vertices are $3, 1, 1, 1$, in order. If we first remove vertex $2$, then remove vertex $3$, and finally remove vertex $4$, the remaining vertex $1$ has no incident edges, so the operations end here. The number of operations is $3$, which is odd, so we print Yes.

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

It may be impossible to perform even $1$ operation.

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

The given graph is not necessarily connected.

Sample 4
Input
8 7
1 2
2 3
4 3
1 3
5 6
8 7
6 7
Output
No

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