問題一覧 > 通常問題

No.1153 ねこちゃんゲーム

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 38
作問者 : Kiri8128Kiri8128 / テスター : tarattata1tarattata1
3 ProblemId : 4619 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-06 23:09:34

問題文

えびちゃんときりちゃんがねこちゃんゲームをします。 ねこちゃんゲームは、木の上でねこちゃんを動かすゲームです。 木は $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もしくは右上の雲マークをクリックしてアカウントを作成してください。