No.2948 move move rotti
レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 75
作問者 : rotti_coder / テスター : nouka28 Michirakara aplysiaSheep t9unkubj
タグ : / 解いたユーザー数 75
作問者 : rotti_coder / テスター : nouka28 Michirakara aplysiaSheep t9unkubj
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。