AT_abc460_f [ABC460F] Farthest Pair Query

$ N $ 頂点の木があります。頂点には $ 1, 2, \ldots, N $ の番号が付けられており、 $ i $ 番目の辺は頂点 $ U_i $ と頂点 $ V_i $ を結んでいます。 はじめ、すべての頂点は黒く塗られています。 以下のクエリを $ Q $ 個順に処理したときの各クエリの答えを求めてください。 - 整数 $ x $ $ (1 \leq x \leq N) $ が与えられる。頂点 $ x $ が白く塗られているならば黒く、黒く塗られているならば白く塗り替える。その後、黒く塗られている頂点どうしの距離の最大値を求める。ただし、木上の $ 2 $ 頂点間の距離とは、その $ 2 $ 頂点を端点とする単純パスに含まれる辺の本数のことを指す。 なお、クエリを順に処理したとき、操作の過程で黒く塗られている頂点が常に $ 2 $ 個以上存在するような入力のみが与えられます。

入力は以下の形式で標準入力から与えられる。ここで $ \text{query}_i $ は $ i $ 番目のクエリを意味する。 > $ N $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_{N-1} $ $ V_{N-1} $ $ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ 各クエリは以下の形式で与えられる。 > $ x $

$ Q $ 行出力せよ。 $ i $ 行目には、クエリを順に処理したときの $ i $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 - $ 1 $ 番目のクエリで色を塗り替えた後、黒く塗られている頂点は $ 2,3,4,5,6,7 $ です。 頂点 $ 4 $ と頂点 $ 6 $ の距離は $ 4 $ であり、答えは $ 4 $ です。 - $ 2 $ 番目のクエリで色を塗り替えた後、黒く塗られている頂点は $ 2,3,5,6,7 $ です。 頂点 $ 2 $ と頂点 $ 6 $ の距離は $ 3 $ であり、答えは $ 3 $ です。 - $ 3 $ 番目のクエリで色を塗り替えた後、黒く塗られている頂点は $ 3,5,6,7 $ です。 頂点 $ 5 $ と頂点 $ 6 $ の距離は $ 3 $ であり、答えは $ 3 $ です。 - $ 4 $ 番目のクエリで色を塗り替えた後、黒く塗られている頂点は $ 3,5,7 $ です。 頂点 $ 5 $ と頂点 $ 7 $ の距離は $ 2 $ であり、答えは $ 2 $ です。 - $ 5 $ 番目のクエリで色を塗り替えた後、黒く塗られている頂点は $ 5,7 $ です。 頂点 $ 5 $ と頂点 $ 7 $ の距離は $ 2 $ であり、答えは $ 2 $ です。 - $ 6 $ 番目のクエリで色を塗り替えた後、黒く塗られている頂点は $ 1,5,7 $ です。 頂点 $ 1 $ と頂点 $ 5 $ の距離は $ 3 $ であり、答えは $ 3 $ です。 - $ 7 $ 番目のクエリで色を塗り替えた後、黒く塗られている頂点は $ 5,7 $ です。 頂点 $ 5 $ と頂点 $ 7 $ の距離は $ 2 $ であり、答えは $ 2 $ です。 - $ 8 $ 番目のクエリで色を塗り替えた後、黒く塗られている頂点は $ 4,5,7 $ です。 頂点 $ 4 $ と頂点 $ 5 $ の距離は $ 3 $ であり、答えは $ 3 $ です。 - $ 9 $ 番目のクエリで色を塗り替えた後、黒く塗られている頂点は $ 4,5,6,7 $ です。 頂点 $ 4 $ と頂点 $ 6 $ の距離は $ 4 $ であり、答えは $ 4 $ です。 上に挙げた例は最大値を達成する一例であることに注意してください。 ### Constraints - $ 3 \leq N \leq 10^5 $ - $ 1 \leq U_i, V_i \leq N $ - 与えられるグラフは木 - $ 1 \leq Q \leq 10^5 $ - 各クエリについて、 $ 1 \leq x \leq N $ - どの時点でも黒く塗られている頂点が $ 2 $ 個以上存在する - 入力される値はすべて整数