問題一覧 > 通常問題

No.3321 岩井星人グラフ-1

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 3
作問者 : のらら / テスター : ゆにたりー卿 DeltaStruct kazuppa elphe Andrew8128 Rice_tawara459 👑 みうね 👑 loop0919 👑 seekworser
お気に入りにしたユーザー ProblemId : 12413 / 自分の提出
問題文最終更新日: 2025-10-30 19:43:57
Iwai Seijin Graph-1
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. Show the original
第2回 岩井星人アンソロジープログラミングコンテスト Div.1 (順位表) の他の問題:

Problem Statement

You are given a simple undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects vertex $A_i$ and vertex $B_i$.

You choose $2$ distinct vertices $i,j(1 \leq i, j \leq N)$ from the $N$ vertices and add exactly $1$ edge between the chosen vertices to create a new graph.

Determine whether there exists a way to choose the $2$ vertices such that the entire graph after adding the edge is an Iwai Seijin graph.


What is an Iwai Seijin graph?

A graph defined by the following conditions is called an Iwai Seijin graph with $X$ arms and arm length $Y$. It was defined in this problem.

  • It is a simple undirected graph consisting of $XY$ vertices and $XY$ edges.
  • It has $X$ vertices of degree $1$, $X(Y−2)$ vertices of degree $2$, and $X$ vertices of degree $3$.
  • For any vertex $v$ of degree $1$, the distance from vertex $v$ to the nearest vertex of degree $3$ is $Y−1$.

Constraints

  • $2 \leq N \leq 3×10^5$
  • $0 \leq M \leq min(N(N-1)/2, 3×10^5)$
  • $1 \leq A_i < B_i \leq N$
  • $(A_i, B_i) \neq (A_j, B_j) \ (i \neq j)$
  • All inputs are integers.

Input

$N\ M$
$A_1\ B_1$
$A_2\ B_2$
:
$A_M\ B_M$

Output

Print Yes if there exists a way to choose the $2$ vertices such that the graph after adding the edge is an Iwai Seijin graph, and No otherwise, followed by a newline.

Sample

Sample 1
Input
9 8
1 2
2 3
1 4
4 5
5 6
4 7
7 8
8 9
Output
Yes

Adding $1$ edge between vertex $1$ and vertex $7$ produces an Iwai Seijin graph with $3$ arms and arm length $3$.

Sample 2
Input
15 14
1 2
2 3
4 5
3 5
6 7
3 7
8 9
9 10
10 11
10 12
11 12
12 15
13 14
14 15
Output
Yes

Adding $1$ edge between vertex $11$ and vertex $15$ produces an Iwai Seijin graph with $5$ arms and arm length $3$.
Although the individual connected components are not Iwai Seijin graphs, the graph as a whole satisfies the conditions of an Iwai Seijin graph, so this is also an Iwai Seijin graph.

Sample 3
Input
15 14
1 2
2 3
1 3
1 4
2 5
3 6
7 8
8 9
7 9
7 10
10 11
12 13
9 14
14 15
Output
No

Adding $1$ edge between vertex $8$ and vertex $12$ makes each connected component an Iwai Seijin graph when viewed individually, but the graph as a whole does not satisfy the conditions of an Iwai Seijin graph, so this is not an Iwai Seijin graph.

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