AT_agc017_d [AGC017D] Game on Tree

[problemUrl]: https://atcoder.jp/contests/agc017/tasks/agc017_d $ N $ 個の頂点 $ 1,\ 2,\ ...,\ N $ からなる木があります． この木の辺は $ (x_i,\ y_i) $ で表されます． Alice と Bob は，この木を使ってゲームをします． Alice から始め，Alice と Bob が交互に次の操作を行います． - まだ残っている辺を選び，その辺を木から取り除く．また，この操作により木は $ 2 $ つに分断されるが，そのうち頂点 $ 1 $ を含まないほうの木も取り除く． 先に操作を行えなくなったほうが負けです． $ 2 $ 人が最適に行動するとき，どちらが勝つかを求めてください．

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 100000 $ - $ 1\ \leq\ x_i,\ y_i\ \leq\ N $ - 与えられるグラフは木である． ### Sample Explanation 1 Alice が最初に頂点 $ 1,\ 2 $ を結ぶ辺を選んで操作を行うと，頂点 $ 1 $ のみを含む木になります． このとき，辺は残っていないので，Bob は操作を行うことができず，Alice が勝ちます．