No.1153 ねこちゃんゲーム
タグ : / 解いたユーザー数 39
作問者 :
Kiri8128
/ テスター :
tarattata1
問題文
えびちゃんときりちゃんがねこちゃんゲームをします。
ねこちゃんゲームは、木の上でねこちゃんを動かすゲームです。
木は $N$ 頂点、 $N-1$ 辺からなります。頂点には $1$ から $N$ の番号が付いていて、
$i\ (1\le i \le N-1)$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。
ねこちゃんは $M$ 匹いて、最初、 $i\ (1\le i\le M)$ 番目のねこちゃんは頂点 $A_i$ にいます。
えびちゃんから始めて交互に次の操作をします。
- ねこちゃんを1匹選び、隣接する頂点に移動させる。 ただし、そのねこちゃんがそれまでにいたことのある頂点に移動させることはできない（ねこちゃんが飽きてしまうので）。
操作ができなくなった人が負けです。そうでない方が勝ちです。
このゲームは、えびちゃんときりちゃんのどちらか一方に必勝法がある（相手の行動によらず必ず勝つ方法がある）ことが示せます。 えびちゃんに必勝法がある場合は、えびちゃんの最初の動かし方のうち最善のもの（必勝法がある状態をキープできる方法）を1つ出力してください。 そうでない場合はそのことを報告してください。
入力
$N\ M$
$A_1\ A_2\ \cdots\ A_M$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$
入力はすべて整数
$1 \le N \le 2 \times 10^5$
$1 \le M \le 2 \times 10^5$
$1 \le u_i,\ v_i\le N\ (1\le i\le N-1)$
$u_i\neq v_i\ (1\le i\le N-1)$
$1 \le A_i\le N\ (1\le i\le M)$
与えられるグラフは木であることが保証される
出力
$i\ v$
$i$ および $v$ は整数で、「 $1\le i\le M$ かつ $1\le v\le N$ 」または $i=v=-1$ を満たす必要があります。
出力の意味は下記のとおりです。
えびちゃんに必勝法がある場合
最初の動かし方のうち最善のものを1つ出力してください。
ただし $i$ 番目のねこちゃんを頂点 $v$ に動かす場合は $i$ と $v$ を空白区切りで出力してください。
最善の方法が複数ある場合はどれを出力しても構いません。
きりちゃんに必勝法がある場合
$i=v=-1$ として "-1 -1" を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
6 1 3 1 2 2 3 3 4 4 5 5 6
出力
1 4
ねこちゃんは1匹で、最初頂点3にいます。
この場合、えびちゃんに必勝法があり、最初のターンで1番目のねこちゃんを頂点4に移動させるのが最善なので、1と4を空白区切りで出力します。
その後の二人の行動は次のとおりです。
- えびちゃんは、最初のターンで1番目のねこちゃんを頂点4に移動させます。（頂点2または頂点4に移動させることができますが、頂点4に移動させるのが最善です。）
- きりちゃんは、1番目のねこちゃんを頂点5に移動させます。頂点3は1番目のねこちゃんが一度いたことがあるので移動させることはできません。
- えびちゃんは、1番目のねこちゃんを頂点6に移動させます。頂点4は1番目のねこちゃんが一度いたことがあるので移動させることはできません。
サンプル2
入力
1 2 1 1
出力
-1 -1
2匹のねこちゃんがいますが、どちらも動かすことはできません。
なお、複数のねこちゃんが同じ頂点にいることもあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。