WeChat Walk

给定 个点 条边的无向图，初始点权 0。 天，每天增加一个点的点权，求每个点点权比周围的点都大的天数。

，点权始终不会超过

按照度数分类，度数大于 的为大点，其余为小点。

大点不会超过 个。

修改点权时，如果是小点，可以暴力更新周围点的情况。

如果是大点，分类讨论：

  1. 周围的大点，不会超过 个，暴力更新。

  2. 周围的小点，不能暴力更新。

    维护 表示大点周围小点权值的最大值，小点更新权值时更新。

    观察数据范围，发现点权只有 ，可以存下大点周围权值为 的有哪些小点是冠军。每次增加点权时暴力扫描权值更新小点。

    容易发现每个大点最多扫描 次。

// Author:  HolyK
// Created: Tue Jul 20 10:22:54 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(2e5 + 5), T(512);
std::vector<int> g[N], big[N], small[N / 512][10001];

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m, q;
  std::cin >> n >> m >> q;
  while (m--) {
    int x, y;
    std::cin >> x >> y;
    x--, y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  std::vector<int> id(n), b;
  for (int i = 0; i < n; i++) {
    if (g[i].size() > T) {
      id[i] = b.size();
      b.push_back(i);
      for (int j : g[i]) {
        big[j].push_back(id[i]);
      }
    }
  }
  std::vector<int> w(n), s(n), max(b.size()), ans(n);
  for (int t = 1; t <= q; t++) {
    int x, y;
    std::cin >> x >> y;
    x--;
    if (g[x].size() <= T) {
      if (!s[x]) {
        int max = 0;
        for (int i : g[x]) {
          smax(max, w[i]);
          if (s[i] && w[x] + y >= w[i]) {
            ans[i] += t - s[i];
            s[i] = 0;
          }
        }
        if (w[x] + y > max) {
          s[x] = t;
        }
      }
      for (int i : big[x]) {
        if (s[x]) small[i][w[x] + y].push_back(x);
        smax(max[i], w[x] + y);
      }
    } else {
      if (!s[x]) {
        int m = max[id[x]];
        for (int v : big[x]) {
          int i = b[v];
          smax(m, w[i]);
          if (s[i] && w[x] + y >= w[i]) {
            ans[i] += t - s[i];
            s[i] = 0;
          }
        }
        if (w[x] + y > m) s[x] = t;
        for (int i = w[x] + y; i > w[x]; i--) {
          for (int j : small[id[x]][i]) {
            if (s[j] && i == w[j]) {
              ans[j] += t - s[j];
              s[j] = 0;
            }
          }
        }
      }
    }
    w[x] += y;
  }
  for (int i = 0; i < n; i++) {
    if (s[i]) {
      ans[i] += q - s[i];
    }
  }
  for (int x : ans) {
    std::cout << x << "\n";
  }
  return 0;
}