問題一覧 > 通常問題

No.2948 move move rotti

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

問題文

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

公園には 11 から NN までの番号が付けられています

また、MM 個の道があり、道 ii は公園 UiU_i と公園 ViV_i を双方向に結んでいます。

rotti君には友達が KK 人います。各 ii について友達 ii は公園 XiX_i にいます。

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

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

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

    制約

    • 1≤N≤151\leq N\leq 15
    • 0≤M≤N(N−1)/20\leq M\leq N(N-1)/2
    • 1≤Ui<Vi≤N1\leq U_i < V_i \leq N
    • 2≤K≤N2\leq K\leq N
    • 1≤Xi≤N1\leq X_i\leq N

    入力

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

    NN MM KK
X1X_1 X2X_2 X3X_3 …\dots XKX_K
U1U_1 V1V_1
U2U_2 V2V_2
⋮\vdots
UMU_M VMV_M

    出力

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

    入出力例

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

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

    サンプル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

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

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