問題一覧 > 通常問題

No.2948 move move rotti

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 92
作問者 : rotti_coder / テスター : nouka28 Michirakara aplysiaSheep t9unkubj
お気に入りにしたユーザー ProblemId : 10807 / 自分の提出
問題文最終更新日: 2024-10-25 17:42:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 451 (並木中等プログラミングコンテスト 2024) (順位表) の他の問題:

Problem Statement

There are $N$ parks in the town where Rotti lives.

The parks are numbered from $1$ to $N$.

There are also $M$ roads, and road $i$ bidirectionally connects park $U_i$ and park $V_i$.

Rotti has $K$ friends. For each $i$, friend $i$ is at park $X_i$.

From now on, the following action is performed $0$ or more times.

  • All people simultaneously move from the park they are currently at to a different adjacent park. However, each person cannot visit a park that they have previously visited.

    • Rotti wants to gather with everyone at one park and play. Determine whether all people can gather at the same vertex with $0$ or more actions.

    Constraints

    • $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$

    Input

    The input is given from standard input in the following format.

    $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$

    Output

    If all people can gather at the same vertex, print Yes; otherwise, print No.

    Sample Input and Output

    Sample 1
    Input
    3 2 2
1 3
1 2
2 3
    Output
    Yes

    On the $1$st action, friend $1$ and friend $2$ should move to park $2$.

    Sample 2
    Input
    5 5 4
2 2 2 2
1 2
2 4
3 5
4 5
1 5
    Output
    Yes

    All friends may be at the same park from the beginning.

    Sample 3
    Input
    4 4 2
1 2
1 2
2 3
3 4
1 4
    Output
    No

    The $2$ people cannot meet.

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