using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
int const NMAX = 2e5 + 11;
int const INF = 1e9 + 100;
vector<int> a, b;
vector<multiset<ii, greater<ii>>>
    bs(NMAX);
multiset<pair<int, int>> ds;
void update(int i, int new_b)
{
    int cur_b = b[i];
    auto it = bs[cur_b].find({a[i], i});
    if (it == bs[cur_b].begin())
    {
        ds.erase({it->first, cur_b});
        if (bs[cur_b].size() == 1)
            ds.insert({INF, cur_b});
        else
            ds.insert({next(bs[cur_b].begin())->first, cur_b});
    }
    bs[cur_b].erase(it);
    if (bs[new_b].empty() or
        a[i] > bs[new_b].begin()->first)
    {
        ds.erase({bs[new_b].empty() ? INF : bs[new_b].begin()->first,
                  new_b});
        ds.insert({a[i], new_b});
    }
    bs[new_b].insert({a[i], i});
    b[i] = new_b;
}
int query(void) { return ds.begin()->first; }
int main(void)
{
    int n, q, i, d;
    cin >> n >> q;
    a.resize(n), b.resize(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i] >> b[i], b[i]--;
        bs[b[i]].insert({a[i], i});
    }
    for (int i = 0; i < NMAX; ++i)
    {
        if (not bs[i].empty())
            ds.insert({bs[i].begin()->first, i});
        else
            ds.insert({INF, i});
    }
    while (q--)
    {
        cin >> i >> d, i--, d--;
        update(i, d);
        cout << query() << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
const int AMAX = 1e6 + 11;
int main(void)
{
    int n;
    vi a, freq;
    cin >> n;
    a.resize(n);
    for (auto &ai : a)
        cin >> ai;
    sort(a.begin(), a.end());
    freq.resize(AMAX);
    freq[a[0]]++;
    int ans = a[0] != a[1];
    for (int i = 1; i < n; ++i)
    {
        bool ok = true;
        if (i < n - 1 and a[i] == a[i + 1])
            ok = false;
        if (ok)
        {
            for (int d = 1; d * d <= a[i]; ++d)
            {
                if (a[i] % d == 0)
                {
                    if (freq[d] or freq[a[i] / d])
                    {
                        ok = false;
                        break;
                    }
                }
            }
        }
        ans += ok;
        freq[a[i]]++;
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
int main(void)
{
    int x, n, y;
    cin >> x >> n;
    set<int> p;
    for (int i = 0; i < n; ++i)
    {
        cin >> y;
        p.insert(y);
    }
    for (int i = 0; i < x + 1; ++i)
    {
        for (auto dir : {-1, +1})
        {
            y = x + dir * i;
            if (p.find(y) == p.end())
            {
                cout << y << endl;
                return 0;
            }
        }
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}

using namespace std;
using ll = long long;
ll solve(int a, int b, int c, int k)
{
    ll ans = 0;
    ans += min(a, k);
    k -= min(a, k);
    if (k == 0)
        return ans;
    k -= min(b, k);
    if (k == 0)
        return ans;
    ans -= min(c, k);
    k -= min(c, k);
    return ans;
}
int main(void)
{
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    cout << solve(a, b, c, k) << endl;
    return 0;
}

using namespace std;
int main(void)
{
    string s, t;
    cin >> s >> t;
    bool ok = s == t.substr(0, t.size() - 1);
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int n, x, y;
    vi cnt;
    cin >> n >> x >> y;
    cnt.resize(n, 0);
    for (int u = 1; u < n; ++u)
    {
        for (int v = u + 1; v <= n; ++v)
        {
            int dist = min({v - u,
                            abs(x - u) + 1 + abs(y - v),
                            abs(x - v) + 1 + abs(y - u)});
            cnt[dist]++;
        }
    }
    for (int k = 1; k < n; ++k)
        cout << cnt[k] << 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 main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n), freq(NMAX, 0);
    read_n(a.begin(), n);
    for (auto ai : a)
        freq[ai]++;
    set<int> uniq(a.begin(), a.end());
    ll ans = 0;
    for (auto x : uniq)
        ans += (ll(freq[x]) * (ll(freq[x]) - 1)) / 2;
    for (auto kai : a)
        cout << ans - freq[kai] + 1 << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int const M = 3;
map<char, int> const id = {{'r', 0}, {'s', 1}, {'p', 2}};
int arg_max(vector<int> v)
{
    return distance(v.begin(), max_element(v.begin(), v.end()));
}
vector<vi> transpose(const vector<vi> &mat)
{
    int n = mat.size(), m = mat[0].size();
    vector<vi> ans(m, vi(n, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            ans[j][i] = mat[i][j];
    return ans;
}
int solve(int n, int k, vector<vi> reward, vi t)
{
    int ans = 0, last;
    vector<vi> reward_T = transpose(reward);
    for (int res = 0; res < k; ++res)
    {
        last = -1;
        for (int i = res; i < n; i += k)
        {
            if (t[i] == last)
            {
                if (i + k < n)
                {
                    for (int j = 0; j < M; ++j)
                        if (j != t[i] and j != t[i + k])
                            last = j;
                }
            }
            else
            {
                last = t[i];
                ans += reward[arg_max(reward_T[t[i]])][t[i]];
            }
        }
    }
    return ans;
}
int main(void)
{
    int n, k;
    string t;
    vi tp;
    vector<vi> reward(M, vi(M, 0));
    cin >> n >> k;
    cin >> reward[0][1] >> reward[1][2] >> reward[2][0];
    cin >> t;
    tp.resize(n);
    for (int i = 0; i < n; ++i)
        tp[i] = id.at(t[i]);
    cout << solve(n, k, reward, tp) << endl;
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vii = vector<ii>;
int const NMAX = 1e5 + 11;
int n, ncolors, color[NMAX];
vii g[NMAX];
void dfs(int u, int p = -1, int c = -1)
{
    int free_color = 1;
    for (auto [v, i] : g[u])
    {
        if (v == p)
            continue;
        if (free_color == c)
            ++free_color;
        color[i] = free_color;
        dfs(v, u, free_color);
        ++free_color;
    }
    ncolors = max(ncolors, free_color - 1);
}
int main(void)
{
    int u, v;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v, u--, v--;
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }
    dfs(1);
    cout << ncolors << endl;
    for (int i = 0; i < n - 1; ++i)
        cout << color[i] << endl;
    return 0;
}