問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 3
作問者 : のらら / テスター : 高橋ゆに DeltaStruct kazuppa elphe Andrew8128 こめだわら みうね 👑 loop0919 seekworser
ProblemId : 12413 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-10-30 19:43:57
コンテストの他の問題:

問題文

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。$i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます。

あなたは $N$ 個の頂点の中から異なる $2$ つの頂点 $i,j(1 \leq i, j \leq N)$ を選び、選んだ頂点の間に辺を $1$ 本だけ追加して新しいグラフを作ります。

このとき、辺を追加した後のグラフ全体が岩井星人グラフになる $2$ つの頂点の選び方が存在するかどうか判定してください。


岩井星人グラフとは

以下の条件で定義されるグラフを、腕の本数 $X$、腕の長さ $Y$ の岩井星人グラフといいます。この問題で定義されたものです。

  • $XY$ 個の頂点と $XY$ 本の辺からなる単純無向グラフである。
  • 次数 $1$ の頂点が $X$ 個、次数 $2$ の頂点が $X(Y−2)$ 個、次数 $3$ の頂点が $X$ 個ある。
  • 任意の次数 $1$ の頂点 $v$ について、頂点 $v$ からの距離が最も短い次数 $3$ の頂点との距離が $Y−1$ である。

制約

  • $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)$
  • 入力は全て整数

入力

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

出力

辺を追加した後のグラフが岩井星人グラフになる $2$ つの頂点の選び方が存在するならばYes、存在しないならばNoを出力し、最後に改行してください。

サンプル

サンプル1
入力
9 8
1 2
2 3
1 4
4 5
5 6
4 7
7 8
8 9
出力
Yes

頂点 $1$ と頂点 $7$ の間に辺を $1$ 本追加すると腕の本数が $3$、腕の長さが $3$ の岩井星人グラフにすることができます。

サンプル2
入力
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
出力
Yes

頂点 $11$ と頂点 $15$ の間に辺を $1$ 本追加すると腕の本数が $5$、腕の長さが $3$ の岩井星人グラフにすることができます。
連結成分ごとに見ると岩井星人グラフではないですが、グラフ全体では岩井星人グラフの条件を満たしているので、これも岩井星人グラフです。

サンプル3
入力
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
出力
No

頂点 $8$ と頂点 $12$ の間に辺を $1$ 本追加すると連結成分ごとに見ればそれぞれ岩井星人グラフになっていますが、 グラフ全体では岩井星人グラフの条件を満たしていないので、これは岩井星人グラフではありません。

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