// Marcin Knapik
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // order_of_key
// #include <ext/pb_ds/tree_policy.hpp> // find by order
// using namespace __gnu_pbds; 
// #define ordered_set tree< int , null_type,less< int >, rb_tree_tag,tree_order_statistics_node_update>  

// const ll MAX_LL = 0xFFFFFFFFFFFFFFFF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_int_distribution<ll>(a, b)(rng)

typedef long double             ld;
typedef long long               ll;
typedef pair<int, int>          ii;
typedef vector<int>             vi;
typedef vector<ll>              vll;
typedef vector<vll>             vvll;
typedef vector<ii>              vii;
typedef vector<vi>              vvi;
typedef vector<vii>             vvii;
#define pll pair<long long, long long>
#define ull unsigned long long

#define sz(a)                   (int)(a).size()
#define pb                      push_back
#define all(c)                  (c).begin(), (c).end()
#define rall(c)                 (c).rbegin(), (c).rend()
#define FOR(i, a)               for (int i = 0; i < (a); i++)
#define f                       first
#define s                       second

template <class T> inline bool setmin(T &a, T b){if (a > b)return a = b, 1;return 0;}
template <class T> inline bool setmax(T &a, T b){if (a < b)return a = b, 1;return 0;}

template<class T> inline T fast(T a,T b,T mod) {ll res = 1; while(b){if(b&1) res = (res*a)%mod;a = (a*a)%mod;b >>= 1;}return res;}
template<class T> istream &operator>>(istream &os, vector<T> &container){for (auto &u : container)os >> u;return os;}
template<class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}
template<class T> inline T gcd(T a, T b) { while (b)swap(a %= b, b); return abs(a); }

const ll INF = 1e9 + 7;
const ll mod = 998244353;
const ll BIG_INF = 1e18 + 7;
const ll N = 2e5+7;
const int T = 1<<20;
const ld inf = 1e18;

const ld eps = 1e-12;

const int LOG = 20;

ll n, m, k, q;

vvi G(N);

int odw[N];
int vis[N];

struct RMQ{
    set<ii> secik;

    void add_pair(ii para){
        set<ii>::iterator it = secik.lower_bound(para);
        while(it != secik.begin()){
            if((*prev(it)).s <= para.s)
                secik.erase(prev(it));
            else
                break;
        }
        if(it == secik.end() or (*it).s < para.s)
            secik.insert(para);

    }

    int val(int gl){
        set<ii>::iterator it = secik.lower_bound({gl, -1});
        if(it == secik.end())
            return 0;
        return (*it).s;
    }
};

int centroid, SS;
int DFS(int s, int p = -1){
    int ret = 1;
    bool ok = 1;

    for(auto & u : G[s])
        if(u != p and !vis[u]){
            int pom = DFS(u, s);
            ok &= (pom * 2 <= SS);
            ret += pom;
        }
    ok &= (ret * 2 >= SS);
    if(ok)   
        centroid = s; 
    return ret;
}

int przodek_centro[N];
vvi odleglosci(N);
RMQ centroidy[N];

void policz_odleglosci(int start, int gl = 1, int p = -1){
    odleglosci[start].pb(gl);
    for(auto & u : G[start])
        if(u != p and !vis[u])
            policz_odleglosci(u, gl + 1, start);
}

void decompose(int start = 1, int p = -1){
    SS = DFS(start);
    DFS(start);

    przodek_centro[centroid] = p;
    vis[centroid] = 1;
    odleglosci[centroid].pb(0);
    // cout << "CENTROID " << centroid << endl;    
    for(auto & u : G[centroid])
        if(!vis[u])
            policz_odleglosci(u);

    int temp_centro = centroid;
    for(auto & u : G[temp_centro])
        if(!vis[u])
            decompose(u, temp_centro);
}

void add_banka(int srodek, int promien, int val){
    int pom = srodek;
    int cnt_odl = sz(odleglosci[srodek]) - 1;
    while(1){
        if(promien - odleglosci[srodek][cnt_odl] >= 0)
            centroidy[pom].add_pair({promien - odleglosci[srodek][cnt_odl], val});
        if(przodek_centro[pom] == -1)
            break;
        pom = przodek_centro[pom];
        cnt_odl--;
    }
}

int ask_centro(int srodek){
    int pom = srodek;
    int ret = 0;
    int cnt_odl = sz(odleglosci[srodek]) - 1;
    while(1){
        ret = max(ret, centroidy[pom].val(odleglosci[srodek][cnt_odl]));
        if(przodek_centro[pom] == -1)
            break;
        pom = przodek_centro[pom];
        cnt_odl--;
    }
    return ret;
}

void solve(){
    cin >> n;

    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;

        G[a].pb(b);
        G[b].pb(a);
    }

    cin >> m;
    queue<int> kol;

    for(int i = 0; i < m; i++){
        int temp;
        cin >> temp;

        kol.push(temp);
        odw[temp] = 1;
    }

    while(sz(kol)){
        int akt = kol.front();
        kol.pop();

        for(auto & u : G[akt]){
            if(!odw[u]){
                odw[u] = odw[akt] + 1;
                kol.push(u);
            }
        }
    }

    decompose();

    for(int i = 1; i <= n; i++)
        if(odw[i] > 1)
            add_banka(i, odw[i] - 2, odw[i] - 1);

    for(int i = 1; i <= n; i++)
        cout << ask_centro(i) << ' ';
    cout << '\n';
}
    
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--)
        solve();
}     
### Prompt

Generate a cpp solution to the following problem:

Alice and Bob are playing a game. They have a tree consisting of n vertices. Initially, Bob has k chips, the i-th chip is located in the vertex a_i (all these vertices are unique). Before the game starts, Alice will place a chip into one of the vertices of the tree.

The game consists of turns. Each turn, the following events happen (sequentially, exactly in the following order):

  1. Alice either moves her chip to an adjacent vertex or doesn't move it; 
  2. for each Bob's chip, he either moves it to an adjacent vertex or doesn't move it. Note that this choice is done independently for each chip. 



The game ends when Alice's chip shares the same vertex with one (or multiple) of Bob's chips. Note that Bob's chips may share the same vertex, even though they are in different vertices at the beginning of the game.

Alice wants to maximize the number of turns, Bob wants to minimize it. If the game ends in the middle of some turn (Alice moves her chip to a vertex that contains one or multiple Bob's chips), this turn is counted.

For each vertex, calculate the number of turns the game will last if Alice places her chip in that vertex.

Input

The first line contains one integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree.

Then n - 1 lines follow, each line contains two integers u_i, v_i (1 ≤ u_i, v_i ≤ n; u_i ≠ v_i) that denote the endpoints of an edge. These edges form a tree.

The next line contains one integer k (1 ≤ k ≤ n - 1) — the number of Bob's chips.

The last line contains k integers a_1, a_2, ..., a_k (1 ≤ a_i ≤ n; a_i ≠ a_j if i ≠ j) — the vertices where the Bob's chips are initially placed.

Output

Print n integers. The i-th of them should be equal to the number of turns the game will last if Alice initially places her chip in the vertex i. If one of Bob's chips is already placed in vertex i, then the answer for vertex i is 0.

Examples

Input


5
2 4
3 1
3 4
3 5
2
4 5


Output


2 1 2 0 0


Input


8
4 1
8 4
4 5
6 4
2 5
4 3
1 7
3
2 8 3


Output


3 0 0 3 1 2 3 0


Input


10
2 5
4 3
7 3
7 2
5 8
3 6
8 10
7 9
7 1
4
10 6 9 1


Output


0 2 2 2 2 0 2 2 0 0

### Response

```cpp
// Marcin Knapik
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // order_of_key
// #include <ext/pb_ds/tree_policy.hpp> // find by order
// using namespace __gnu_pbds; 
// #define ordered_set tree< int , null_type,less< int >, rb_tree_tag,tree_order_statistics_node_update>  

// const ll MAX_LL = 0xFFFFFFFFFFFFFFFF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_int_distribution<ll>(a, b)(rng)

typedef long double             ld;
typedef long long               ll;
typedef pair<int, int>          ii;
typedef vector<int>             vi;
typedef vector<ll>              vll;
typedef vector<vll>             vvll;
typedef vector<ii>              vii;
typedef vector<vi>              vvi;
typedef vector<vii>             vvii;
#define pll pair<long long, long long>
#define ull unsigned long long

#define sz(a)                   (int)(a).size()
#define pb                      push_back
#define all(c)                  (c).begin(), (c).end()
#define rall(c)                 (c).rbegin(), (c).rend()
#define FOR(i, a)               for (int i = 0; i < (a); i++)
#define f                       first
#define s                       second

template <class T> inline bool setmin(T &a, T b){if (a > b)return a = b, 1;return 0;}
template <class T> inline bool setmax(T &a, T b){if (a < b)return a = b, 1;return 0;}

template<class T> inline T fast(T a,T b,T mod) {ll res = 1; while(b){if(b&1) res = (res*a)%mod;a = (a*a)%mod;b >>= 1;}return res;}
template<class T> istream &operator>>(istream &os, vector<T> &container){for (auto &u : container)os >> u;return os;}
template<class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}
template<class T> inline T gcd(T a, T b) { while (b)swap(a %= b, b); return abs(a); }

const ll INF = 1e9 + 7;
const ll mod = 998244353;
const ll BIG_INF = 1e18 + 7;
const ll N = 2e5+7;
const int T = 1<<20;
const ld inf = 1e18;

const ld eps = 1e-12;

const int LOG = 20;

ll n, m, k, q;

vvi G(N);

int odw[N];
int vis[N];

struct RMQ{
    set<ii> secik;

    void add_pair(ii para){
        set<ii>::iterator it = secik.lower_bound(para);
        while(it != secik.begin()){
            if((*prev(it)).s <= para.s)
                secik.erase(prev(it));
            else
                break;
        }
        if(it == secik.end() or (*it).s < para.s)
            secik.insert(para);

    }

    int val(int gl){
        set<ii>::iterator it = secik.lower_bound({gl, -1});
        if(it == secik.end())
            return 0;
        return (*it).s;
    }
};

int centroid, SS;
int DFS(int s, int p = -1){
    int ret = 1;
    bool ok = 1;

    for(auto & u : G[s])
        if(u != p and !vis[u]){
            int pom = DFS(u, s);
            ok &= (pom * 2 <= SS);
            ret += pom;
        }
    ok &= (ret * 2 >= SS);
    if(ok)   
        centroid = s; 
    return ret;
}

int przodek_centro[N];
vvi odleglosci(N);
RMQ centroidy[N];

void policz_odleglosci(int start, int gl = 1, int p = -1){
    odleglosci[start].pb(gl);
    for(auto & u : G[start])
        if(u != p and !vis[u])
            policz_odleglosci(u, gl + 1, start);
}

void decompose(int start = 1, int p = -1){
    SS = DFS(start);
    DFS(start);

    przodek_centro[centroid] = p;
    vis[centroid] = 1;
    odleglosci[centroid].pb(0);
    // cout << "CENTROID " << centroid << endl;    
    for(auto & u : G[centroid])
        if(!vis[u])
            policz_odleglosci(u);

    int temp_centro = centroid;
    for(auto & u : G[temp_centro])
        if(!vis[u])
            decompose(u, temp_centro);
}

void add_banka(int srodek, int promien, int val){
    int pom = srodek;
    int cnt_odl = sz(odleglosci[srodek]) - 1;
    while(1){
        if(promien - odleglosci[srodek][cnt_odl] >= 0)
            centroidy[pom].add_pair({promien - odleglosci[srodek][cnt_odl], val});
        if(przodek_centro[pom] == -1)
            break;
        pom = przodek_centro[pom];
        cnt_odl--;
    }
}

int ask_centro(int srodek){
    int pom = srodek;
    int ret = 0;
    int cnt_odl = sz(odleglosci[srodek]) - 1;
    while(1){
        ret = max(ret, centroidy[pom].val(odleglosci[srodek][cnt_odl]));
        if(przodek_centro[pom] == -1)
            break;
        pom = przodek_centro[pom];
        cnt_odl--;
    }
    return ret;
}

void solve(){
    cin >> n;

    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;

        G[a].pb(b);
        G[b].pb(a);
    }

    cin >> m;
    queue<int> kol;

    for(int i = 0; i < m; i++){
        int temp;
        cin >> temp;

        kol.push(temp);
        odw[temp] = 1;
    }

    while(sz(kol)){
        int akt = kol.front();
        kol.pop();

        for(auto & u : G[akt]){
            if(!odw[u]){
                odw[u] = odw[akt] + 1;
                kol.push(u);
            }
        }
    }

    decompose();

    for(int i = 1; i <= n; i++)
        if(odw[i] > 1)
            add_banka(i, odw[i] - 2, odw[i] - 1);

    for(int i = 1; i <= n; i++)
        cout << ask_centro(i) << ' ';
    cout << '\n';
}
    
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--)
        solve();
}     
```