AT_codequeen2023_final_c Path Intersection

頂点に $ 1, 2, \ldots, N $ の番号がついた $ N $ 頂点の木と、頂点の番号 $ S, T $ が与えられます。 $ i = 1, 2, \ldots, N-1 $ について、 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 木のそれぞれの頂点 $ j $ について、以下の質問に答えてください。 - 頂点 $ S $ から頂点 $ j $ までの最短経路に含まれる頂点集合（頂点 $ S $ や頂点 $ j $ を含む）と、頂点 $ T $ から頂点 $ j $ までの最短経路に含まれる頂点集合（頂点 $ T $ や頂点 $ j $ を含む）の両方に属する頂点の数はいくつでしょうか？

入力は以下の形式で標準入力から与えられます。 > $ N $ $ S $ $ T $ $ u_1 $ $ v_1 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

$ N $ 行出力してください。 $ i $ 行目には、頂点 $ i $ に関する質問の答えを出力してください。

### Sample Explanation 1 この入力例では、 $ S = 1, T = 4 $ です。 - $ j = 1 $ のとき - $ S $ から $ j $ までの最短経路に含まれる頂点集合は $ \left\{ 1 \right\} $ です。 - $ T $ から $ j $ までの最短経路に含まれる頂点集合は $ \left\{ 1, 2, 4 \right\} $ です。 - 両方に属するのは、頂点 $ 1 $ のみなので、答えは $ 1 $ です。 - $ j = 5 $ のとき - $ S $ から $ j $ までの最短経路に含まれる頂点集合は $ \left\{ 1, 2, 3, 5 \right\} $ です。 - $ T $ から $ j $ までの最短経路に含まれる頂点集合は $ \left\{ 2, 3, 4, 5 \right\} $ です。 - 両方に属するのは、頂点 $ 2, 3, 5 $ なので、答えは $ 3 $ です。 ### Constraints - 入力はすべて整数で与えられる - $ 3 \leq N \leq 200{,}000 $ - $ 1 \leq S, T \leq N $ - $ S \neq T $ - $ 1 \leq u_i, v_i \leq N $ $ (1 \leq i \leq N-1) $ - 与えられるグラフは木である