問題一覧 > 通常問題

No.1983 [Cherry 4th Tune C] 南の島のマーメイド

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : 👑 KazunKazun / テスター : akakimidoriakakimidori potato167potato167
1 ProblemId : 5209 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-17 20:22:31

問題文

ゼルコバの国は $N$ 個の島からなる島国である. この $N$ 個の島は島 $1, \dots,$ 島 $N$ と名付けられている.

人魚のチェリーちゃんは $a=u_i, b=v_i$ となる $1$ 以上 $M$ 以下の整数 $i$ が存在するとき, そしてそのときに限り, 島 $a$ と島 $b$ を双方向に行き来できる.

迷子になりやすいチェリーちゃんはどの島からどの島へ移動するときに迷子になりにくいかを調べることにした.

次の $Q$ 個の質問に答えよ. ただし, $q$ 番目の質問は整数の組 $(x_q, y_q)$ で与えられる.

質問 $q$

以下の条件を全て満たす整数の列 $(p_0, p_1, \dots, p_k)$ は唯一存在するか?

  • $k \geq 1$
  • $1 \leq p_i \leq N$
  • $p_0=x_q, p_k=y_q$
  • $p_0, p_1, \dots, p_k$ は全て異なる.
  • チェリーちゃんは 島 $p_{i-1}$ と島 $p_i$ を双方向に行き来できる.

制約

  • $2 \leq N \leq 2 \times 10^5$
  • $0 \leq M \leq \min(\frac{1}{2}N(N-1), 2 \times 10^5)$
  • $1 \leq Q \leq 2 \times 10^5$
  • $1 \leq u_i \leq N, 1 \leq v_i \leq N$
  • $u_i \neq v_i$
  • $i \neq j \Rightarrow (u_i, v_i) \neq (u_j, v_j), (u_i, v_i) \neq (v_j, u_j)$
  • $1 \leq x_q \leq N, 1 \leq y_q \leq N$
  • $x_q \neq y_q$
  • 入力は全て整数である.

入力

$N$ $M$ $Q$
$u_1$ $v_1$
$\vdots$
$u_M$ $v_M$
$x_1$ $y_1$
$\vdots$
$x_Q$ $y_Q$

出力

出力は $Q$ 行からなる. $q~(1 \leq q \leq Q)$ 行目には質問 $q$ において唯一存在するならば Yes, そうでないならば No と出力せよ.

最後に改行を忘れないこと.

サンプル

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

チェリーちゃんは以下の図において, 矢印で繋がっている2つの島同士を行き来できる.

  • $1$ 問目は $(x_1, y_1)=(1,4)$ である. これは $(1,4)$ が条件を満たす唯一の整数列であるため, 答えは Yes である.
  • $2$ 問目は $(x_2, y_2)=(1,2)$ である. これは $(1,2)$ 及び, $(1,3,2)$ という条件を満たす異なる2つの整数列が存在するため, 答えは No である.
  • $3$ 問目は $(x_3 ,y_3)=(1,7)$ である. そもそも条件を満たす整数列が存在しないので, 答えは No である.

サンプル2
入力
4 0 4
1 2
2 3
3 4
4 1
出力
No
No
No
No

チェリーちゃんは島の行き来ができない可能性がある.

サンプル2
入力
5 4 5
1 2
1 3
1 4
1 5
1 3
3 5
2 4
3 1
1 3
出力
Yes
Yes
Yes
Yes
Yes

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