using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int const NMAX = 2e5 + 11;
int const LMAX = 20;
int n, timer, val[NMAX], tin[NMAX], tout[NMAX], up[NMAX][LMAX], ans[NMAX];
vi g[NMAX];
void preprocess(int u, int p)
{
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i < LMAX; ++i)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto v : g[u])
        if (v != p)
            preprocess(v, u);
    tout[u] = ++timer;
}
void solve(int u, int p)
{
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        solve(v, u);
        val[u] += val[v];
    }
    ans[u] = val[u];
}
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = LMAX - 1; i >= 0; --i)
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    return up[u][0];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int m;
    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int root = 1;
    preprocess(root, root);
    while (m--)
    {
        int u, v, l;
        cin >> u >> v;
        val[u] += 1;
        val[v] += 1;
        l = lca(u, v);
        val[l] -= 1;
        if (l != root)
            val[up[l][0]] -= 1;
    }
    solve(1, 1);
    write(ans + 1, ans + n + 1, " "), cout << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int const NMAX = 2e5 + 11;
int const LMAX = 20;
int n, timer, tin[NMAX], tout[NMAX], up[NMAX][LMAX], depth[NMAX];
vi g[NMAX];
void dfs(int u, int p)
{
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i < LMAX; ++i)
    {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int v : g[u])
    {
        if (v != p)
        {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
    tout[u] = ++timer;
}
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] and tout[u] >= tout[v];
}
int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = LMAX - 1; i >= 0; --i)
    {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1);
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        cout << depth[u] + depth[v] - 2 * depth[lca(u, v)] << endl;
    }
    return 0;
}

using namespace std;
int const AMAX = 1e4 + 11;
int main(void)
{
    int t;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc)
    {
        int n;
        cin >> n;
        vector<set<int>> stamps(n);
        vector<int> cnt(AMAX, 0), ans(n, 0);
        for (int i = 0; i < n; ++i)
        {
            int m, x;
            cin >> m;
            while (m--)
            {
                cin >> x;
                stamps[i].insert(x);
            }
            for (auto x : stamps[i])
                cnt[x]++;
        }
        for (int i = 0; i < n; ++i)
            for (auto x : stamps[i])
                ans[i] += (cnt[x] == 1);
        int total = accumulate(ans.begin(), ans.end(), 0);
        cout << "Case " << tc << ": ";
        for (int i = 0; i < n; ++i)
            cout << fixed << setprecision(6) << (ans[i] * 100.0) / (double)total
                 << "%" << (i < n - 1 ? " " : "");
        cout << endl;
    }
    return 0;
}

using namespace std;
inline string format_dollar(int cents)
{
    stringstream ss;
    int dollars = cents / 100;
    cents = cents % 100;
    ss << dollars << "." << setw(2) << setfill('0') << cents << "$";
    return ss.str();
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int k, m;
        map<char, int> value;
        string s;
        cin >> k;
        while (k--)
        {
            char c;
            cin >> c;
            cin >> value[c];
        }
        cin >> m;
        cin.ignore();
        int cents = 0;
        while (m--)
        {
            getline(cin, s);
            cents = accumulate(s.begin(), s.end(), cents, [&value](int acc, char c) {
                return acc + value[c];
            });
        }
        cout << format_dollar(cents) << endl;
    }
    return 0;
}

using namespace std;
using lld = long double;
using mdi = map<lld, int>;
const int NMAX = 2 * 10e5 + 11;
int n;
lld a[NMAX], b[NMAX];
mdi counter;
bool comp(const pair<lld, int> &l, const pair<lld, int> &r)
{
    return l.second < r.second;
}
int main(void)
{
    int zeros = 0;
    lld frac;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == 0 and b[i] == 0)
            ++zeros;
        if (a[i] == 0)
            continue;
        else
        {
            frac = b[i] / a[i];
            ++counter[frac];
        }
    }
    cout << zeros + max_element(counter.begin(), counter.end(), comp)->second
         << endl;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
ll n, dp[NMAX], sz[NMAX], ans[NMAX];
vi g[NMAX];
void dfs(int u, int p = -1)
{
    sz[u] = 1;
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        dfs(v, u);
        sz[u] += sz[v];
        dp[u] += dp[v] + sz[v];
    }
}
void reroot(int u, int p = -1)
{
    ans[u] = dp[u];
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        auto temp1 = dp[v], temp2 = sz[v];
        dp[v] = dp[u] + sz[u] - 2 * sz[v];
        sz[v] = sz[u];
        reroot(v, u);
        dp[v] = temp1;
        sz[v] = temp2;
    }
}
int main(void)
{
    int root = 1;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(root);
    reroot(root);
    for (int i = 1; i <= n; ++i)
    {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n, ddown[NMAX], ans[NMAX];
vi g[NMAX];
void dp(int u, int p = -1)
{
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        dp(v, u);
        ddown[u] = max(ddown[u], ddown[v] + 1);
    }
}
void reroot(int u, int p = -1, int dup = 0)
{
    ans[u] = max(ddown[u], dup);
    vector<ii> dists = {{dup, -1}, {0, -1}};
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        dists.emplace_back(ddown[v] + 1, v);
    }
    sort(dists.begin(), dists.end(), greater<ii>());
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        reroot(v,
               u,
               dists[0].second == v ? dists[1].first + 1 : dists[0].first + 1);
    }
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dp(1);
    reroot(1);
    for (int u = 1; u <= n; ++u)
        cout << ans[u] << " ";
    cout << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n;
vi g[NMAX];
ii dfs(int u, int p, int d)
{
    ii ans = {d, u};
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        ans = max(ans, dfs(v, u, d + 1));
    }
    return ans;
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto [d1, u] = dfs(1, 0, 0);
    auto [d2, v] = dfs(u, 0, 0);
    cout << d2 << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int n, m;
    vi f;
    vector<vi> bs;
    cin >> n >> m;
    f.resize(n, 0), bs.resize(n);
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b, --a, --b;
        bs[a].push_back(b);
    }
    auto dist = [n](int l, int r) -> int { return (r - l + n) % n; };
    for (int i = 0; i < n; ++i)
    {
        if ((int)bs[i].size() > 0)
        {
            int closest = *min_element(bs[i].begin(), bs[i].end(), [i, dist](int a, int b) {
                return dist(i, a) < dist(i, b);
            });
            f[i] = ((int)bs[i].size() - 1) * n + dist(i, closest);
        }
    }
    for (int start = 0; start < n; ++start)
    {
        int ans = 0;
        for (int delta = 0; delta < n; ++delta)
        {
            auto fi = f[(start + delta) % n];
            ans = max(ans, fi + (fi > 0) * delta);
        }
        cout << ans << " ";
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int const NMAX = 2e5 + 11;
int n, dp1[NMAX], dp2[NMAX];
vi g[NMAX];
void solve(int u, int p = 0)
{
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        solve(v, u);
        dp2[u] += max(dp1[v], dp2[v]);
    }
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        auto v_choice = max(dp1[v], dp2[v]);
        dp1[u] = max(dp1[u], 1 + dp2[u] - v_choice + dp2[v]);
    }
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int root = 1;
    solve(root);
    cout << max(dp1[root], dp2[root]) << endl;
    return 0;
}