树上差分：把「整条路径 +1」变成「四个格子 ±1」

// 暴力：每条路径老老实实走一遍，路过哪个点就给哪个点 +1
//
// 一条路径 u—v 怎么走：两个端点比深度，深的那个先往上爬，爬到一样深之后一起往上，
// 直到撞在一起（那个点就是 LCA）—— 和第 51 章第 2 步的暴力是同一段代码，
// 只是这里不光要知道撞在哪，还要把沿途每个点都 +1。
//
// ⇒ 一条路径的代价是**它自己的长度**。所以慢不慢完全看树长什么样：
//   随机树的路径平均只有几十个点，链上却能有几十万个 —— 正文第 3 步量了这笔账。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;

int dep[MAXN], fa[MAXN], bfs[MAXN];
long long cnt[MAXN];
vector<int> g[MAXN];
int n, m, root;

void build() {
    vector<char> vis(n + 1, 0);
    int head = 0, tail = 0;
    dep[root] = 0;
    fa[root] = 0;
    vis[root] = 1;
    bfs[tail++] = root;
    while (head < tail) {
        int u = bfs[head++];
        for (int v : g[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
            dep[v] = dep[u] + 1;
            fa[v] = u;
            bfs[tail++] = v;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build();
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        while (dep[u] > dep[v]) { cnt[u]++; u = fa[u]; }
        while (dep[v] > dep[u]) { cnt[v]++; v = fa[v]; }
        while (u != v) { cnt[u]++; cnt[v]++; u = fa[u]; v = fa[v]; }
        cnt[u]++;                         // ⚠ 撞在一起的那个点（LCA）只加一次
    }
    long long best = 0;
    for (int v = 1; v <= n; v++) {
        cout << cnt[v] << (v == n ? '\n' : ' ');
        best = max(best, cnt[v]);
    }
    cout << best << '\n';
    return 0;
}

// 换一把尺子：数「一共碰了多少格」
//
// ★ 为什么需要它：这一章的秒表在小数据上全是 0.00 秒，而**碰格数**是能数出来的、
//   换台机器也不变的东西。两种做法各放一个计数器，数的是同一个动作：**给某个格子 ±1**。
//     · 暴力：路径经过几个点就碰几格 ⇒ 总数 = 所有路径的**长度之和**；
//     · 差分：每条路径固定碰 4 格（四个标记），最后还原时每个点碰一次 ⇒ 总数 = 4m + (n−1)。
//   ⇒ 后者**和树的形状无关**，前者完全被形状牵着走 —— 正文第 3 步那张表就是这么来的。
//
// 顺带把这组数据的几个性质量出来（正文第 12 步要用）：
//   最大深度、平均路径长度、「LCA 恰好是根」的比例、「两端是同一个点」的比例。
//
// 用法：./count < 输入        （和主程序同一份输入）
//       ./count csv < 输入    只打 `键,值`，给 check:viz 用

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int LOG = 20;

int up[LOG][MAXN];
int dep[MAXN], fa[MAXN], bfs_[MAXN];
long long d[MAXN];
vector<int> g[MAXN];
int n, m, root;

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int t = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++) if ((t >> k) & 1) u = up[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--) if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    return up[0][u];
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    cin >> n >> m >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    {
        vector<char> vis(n + 1, 0);
        int head = 0, tail = 0;
        fa[root] = 0;
        up[0][root] = root;
        vis[root] = 1;
        bfs_[tail++] = root;
        while (head < tail) {
            int u = bfs_[head++];
            for (int v : g[u])
                if (!vis[v]) { vis[v] = 1; dep[v] = dep[u] + 1; fa[v] = u; up[0][v] = u; bfs_[tail++] = v; }
        }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++) up[k][v] = up[k - 1][up[k - 1][v]];

    int maxDep = 0;
    for (int v = 1; v <= n; v++) maxDep = max(maxDep, dep[v]);

    long long touchBrute = 0, rootLca = 0, samePair = 0, sumLen = 0;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        int p = lca(u, v);
        long long len = dep[u] + dep[v] - 2LL * dep[p] + 1;   // 这条路径上有几个点
        sumLen += len;
        touchBrute += len;                                    // 暴力就是一格一格地碰
        if (p == root) rootLca++;
        if (u == v) samePair++;
        d[u]++; d[v]++; d[p]--; if (fa[p]) d[fa[p]]--;
    }
    long long touchFast = 4LL * m + (n - 1);                  // 四个标记 + 还原一趟
    long long best = 0;
    for (int i = n - 1; i >= 1; i--) { int u = bfs_[i]; d[fa[u]] += d[u]; }
    for (int v = 1; v <= n; v++) best = max(best, d[v]);

    double avgLen = (double)sumLen / m;
    if (csv) {
        cout << "maxdep," << maxDep << '\n';
        cout << "avglen," << fixed << setprecision(2) << avgLen << '\n';
        cout << "brute," << touchBrute << '\n';
        cout << "fast," << touchFast << '\n';
        cout << "rootlca," << (long long)llround(1000.0 * rootLca / m) << '\n';
        cout << "same," << (long long)llround(1000.0 * samePair / m) << '\n';
        cout << "best," << best << '\n';
    } else {
        cout << "点数 n = " << n << "，路径 m = " << m << "，根 = " << root << '\n';
        cout << "最大深度            " << maxDep << '\n';
        cout << "平均每条路径几个点  " << fixed << setprecision(2) << avgLen << '\n';
        cout << "暴力一共碰了几格    " << touchBrute << '\n';
        cout << "差分一共碰了几格    " << touchFast << "   （4m + n−1，和树的形状无关）\n";
        cout << "差了几倍            " << fixed << setprecision(2)
             << (double)touchBrute / touchFast << '\n';
        cout << "最大覆盖次数        " << best << '\n';
    }
    return 0;
}

// 正解：树上差分（点差分）—— m 条路径整条 +1，最后一趟求出每个点被覆盖多少次
//
// ★ 关键的一步和第 6 章的一维差分是同一件事，只换了「前缀和」这个词：
//
//     一维：区间 [l, r] 全 +1  ⇒  d[l]++、d[r+1]--   ，最后做一遍**前缀和**还原
//     树上：路径 u—v 全 +1     ⇒  在四个点上打标记，最后做一遍**子树和**还原
//
//   四个标记是（设 p = lca(u, v)）：
//
//       d[u]++ ; d[v]++ ; d[p]-- ; d[fa[p]]--
//
//   为什么是这四个：把「子树和」想成「从这个点一直往上加到根」的逆运算 ——
//   d[u]++ 让 u 到根这一条链全 +1，d[v]++ 让 v 到根这一条链全 +1，
//   于是 p 到根那一段被加了**两遍**，而路径本来只经过 p 一次、根本不经过 p 的祖先。
//   ⇒ d[p]-- 把 p 多出来的那一次减掉；d[fa[p]]-- 把 p 以上整段多出来的两次里的第二次减掉。
//
// ⚠⚠ 根的父亲在这里**不能沿用第 51 章「根的父亲是它自己」那个约定** ——
//   路径的 LCA 恰好是根时，d[root]-- 和 d[fa[root]]-- 会落在同一个点上，根就被减了两次。
//   这里让 fa[root] = 0，而 0 号是个不存在的点，减在它身上没人看得见。
//   （wrongFaRoot.cpp 就是照搬那个约定写的，正文第 10 步拿它对拍。）
//
// ⚠ 还原那一趟**按 BFS 序倒着扫**，不要递归 —— 理由和第 51 章第 9 步一模一样：
//   最坏形状是一条链，50 万层递归必然段错误。BFS 序倒着扫，儿子一定排在父亲后面，
//   所以「加给父亲」的时候，这个点自己的子树和已经算完了。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int LOG = 20;                       // 2^19 = 524288 > 5×10^5

int up[LOG][MAXN];
int dep[MAXN], fa[MAXN], bfs[MAXN];
long long d[MAXN];
vector<int> g[MAXN];
int n, m, root;

void build() {
    vector<char> vis(n + 1, 0);
    int head = 0, tail = 0;
    dep[root] = 0;
    fa[root] = 0;                         // ⚠ 不是 root 自己，是不存在的 0 号点
    up[0][root] = root;                   // 倍增表照旧用「根的父亲是自己」，两者不冲突
    vis[root] = 1;
    bfs[tail++] = root;
    while (head < tail) {
        int u = bfs[head++];
        for (int v : g[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
            dep[v] = dep[u] + 1;
            fa[v] = u;
            up[0][v] = u;
            bfs[tail++] = v;
        }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int t = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if ((t >> k) & 1) u = up[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    return up[0][u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build();
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        int p = lca(u, v);
        d[u]++;
        d[v]++;
        d[p]--;
        d[fa[p]]--;                       // ⚠ p 是根时落在 0 号点上，正好没人看得见
    }
    for (int i = n - 1; i >= 1; i--) {    // ★ BFS 序倒着扫 = 从叶子往根累加
        int u = bfs[i];
        d[fa[u]] += d[u];
    }
    long long best = 0;
    for (int v = 1; v <= n; v++) {
        cout << d[v] << (v == n ? '\n' : ' ');
        best = max(best, d[v]);
    }
    cout << best << '\n';
    return 0;
}

// 正解：树上差分（点差分）—— m 条路径整条 +1，最后一趟求出每个点被覆盖多少次
//
// ★ 关键的一步和第 6 章的一维差分是同一件事，只换了「前缀和」这个词：
//
//     一维：区间 [l, r] 全 +1  ⇒  d[l]++、d[r+1]--   ，最后做一遍**前缀和**还原
//     树上：路径 u—v 全 +1     ⇒  在四个点上打标记，最后做一遍**子树和**还原
//
//   四个标记是（设 p = lca(u, v)）：
//
//       d[u]++ ; d[v]++ ; d[p]-- ; d[fa[p]]--
//
//   为什么是这四个：把「子树和」想成「从这个点一直往上加到根」的逆运算 ——
//   d[u]++ 让 u 到根这一条链全 +1，d[v]++ 让 v 到根这一条链全 +1，
//   于是 p 到根那一段被加了**两遍**，而路径本来只经过 p 一次、根本不经过 p 的祖先。
//   ⇒ d[p]-- 把 p 多出来的那一次减掉；d[fa[p]]-- 把 p 以上整段多出来的两次里的第二次减掉。
//
// ⚠⚠ 根的父亲在这里**不能沿用第 51 章「根的父亲是它自己」那个约定** ——
//   路径的 LCA 恰好是根时，d[root]-- 和 d[fa[root]]-- 会落在同一个点上，根就被减了两次。
//   这里让 fa[root] = 0，而 0 号是个不存在的点，减在它身上没人看得见。
//   （wrongFaRoot.cpp 就是照搬那个约定写的，正文第 10 步拿它对拍。）
//
// ⚠ 还原那一趟**按 BFS 序倒着扫**，不要递归 —— 理由和第 51 章第 9 步一模一样：
//   最坏形状是一条链，50 万层递归必然段错误。BFS 序倒着扫，儿子一定排在父亲后面，
//   所以「加给父亲」的时候，这个点自己的子树和已经算完了。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
const int LOG = 20;                       // 2^19 = 524288 > 5×10^5

int up[LOG][MAXN];
int dep[MAXN], fa[MAXN], bfs[MAXN];
long long d[MAXN];
vector<int> g[MAXN];
int n, m, root;

void build() {
    vector<char> vis(n + 1, 0);
    int head = 0, tail = 0;
    dep[root] = 0;
    fa[root] = 0;                         // ⚠ 不是 root 自己，是不存在的 0 号点
    up[0][root] = root;                   // 倍增表照旧用「根的父亲是自己」，两者不冲突
    vis[root] = 1;
    bfs[tail++] = root;
    while (head < tail) {
        int u = bfs[head++];
        for (int v : g[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
            dep[v] = dep[u] + 1;
            fa[v] = u;
            up[0][v] = u;
            bfs[tail++] = v;
        }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int t = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if ((t >> k) & 1) u = up[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    return up[0][u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> root;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build();
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        int p = lca(u, v);
        d[u]++;
        d[v]++;
        d[p]--;
        d[fa[p]]--;                       // ⚠ p 是根时落在 0 号点上，正好没人看得见
    }
    for (int i = n - 1; i >= 1; i--) {    // ★ BFS 序倒着扫 = 从叶子往根累加
        int u = bfs[i];
        d[fa[u]] += d[u];
    }
    long long best = 0;
    for (int v = 1; v <= n; v++) {
        cout << d[v] << (v == n ? '\n' : ' ');
        best = max(best, d[v]);
    }
    cout << best << '\n';
    return 0;
}