AT_agc033_c [AGC033C] Removing Coins

[problemUrl]: https://atcoder.jp/contests/agc033/tasks/agc033_c 高橋君と青木君は木を用いてゲームをすることにしました。 ゲームに用いる木は $ N $ 頂点からなり、各頂点には $ 1 $ から $ N $ の番号が割り振られています。 また、$ N-1 $ 本の辺のうち、 $ i $ 本目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 ゲーム開始時、各頂点にはコインが一枚ずつ置いてあります。 高橋君と青木君は高橋君から始めて以下の操作を交互に行い、操作を行えなくなった方が負けになります。 - コインが置いてある頂点を一つ選び、その頂点 $ v $ に置いてあるコインをすべて取り除く。 - その後、木上に残っているコインをすべて、今置いてある頂点に隣接する頂点のうち $ v $ に一番近い頂点に移動させる。 つまり、木上にコインが残っていない状態で手番となった人の負けです。 二人が最適に行動したとき、どちらが勝つか求めてください。

N/A

N/A

### 制約 - $ 1\ ≦\ N\ ≦\ 2\ \times\ 10^5 $ - $ 1\ ≦\ a_i,\ b_i\ ≦\ N $ - $ a_i\ \neq\ b_i $ - 入力で与えられるグラフは木である。 ### Sample Explanation 1 ゲームは例えば以下のように進行します。 - 高橋君が頂点 $ 1 $ からコインを取り除く。操作後は、頂点 $ 1 $ に一つ、頂点 $ 2 $ に一つコインがある。 - 青木君が頂点 $ 2 $ からコインを取り除く。操作後は、頂点 $ 2 $ に一つコインがある。 - 高橋君が頂点 $ 2 $ からコインを取り除く。操作後は、木上にコインは残っていない。 - 青木君は木上にコインがない状態で手番となってしまったので、負けとなる。