問題一覧 > 通常問題

No.2948 move move rotti

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : rotti_coderrotti_coder / テスター : nouka28nouka28 MichirakaraMichirakara aplysiaSheepaplysiaSheep t9unkubjt9unkubj
1 ProblemId : 10807 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-25 17:42:58

問題文

rotti君の住む町には $N$ 個の公園があります。

公園には $1$ から $N$ までの番号が付けられています

また、$M$ 個の道があり、道 $i$ は公園 $U_i$ と公園 $V_i$ を双方向に結んでいます。

rotti君には友達が $K$ 人います。各 $i$ について友達 $i$ は公園 $X_i$ にいます。

これから $0$ 回以上の次の行動を行います。

  • すべての人が同時に今いる公園に隣接する別の公園に移動する。ただし、それぞれの人は以前自分が訪れたことのある公園を訪れることができない。

    • rotti君は、みんなと一つの公園に集まって遊びたくなりました。$0$ 回以上の行動ですべての人が同じ頂点に集合することができるか判定してください。

    制約

    • $1\leq N\leq 15$
    • $0\leq M\leq N(N-1)/2$
    • $1\leq U_i < V_i \leq N$
    • $2\leq K\leq N$
    • $1\leq X_i\leq N$

    入力

    入力は以下の形式で標準入力から与えられる。

    $N$ $M$ $K$
$X_1$ $X_2$ $X_3$ $\dots$ $X_K$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

    出力

    すべての人が同じ頂点に集合することができるとき、Yes そうでなければ、 No を出力してください。

    入出力例

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

    $1$ 回目の行動の時に友達 $1$、友達 $2$ が公園 $2$に移動すればよいです。

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

    最初からすべての友達が同じ公園にいる場合もあります。

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

    $2$ 人は出会うことができません。

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