#include using namespace std; typedef pair P; struct Union_Find { //各要素が属する集合の代表(根)を管理する //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい vector data; Union_Find(int size) : data(size, -1) {} bool Union(int x, int y) { x = Find(x); y = Find(y); bool is_union = (x != y); if (is_union) { if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; } return is_union; } int Find(int x) { if (data[x] < 0) { //要素xが根である return x; } else { data[x] = Find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される return data[x]; } } bool same(int x, int y) { return Find(x) == Find(y); } int size(int x) { return -data[Find(x)]; } }; void setter(vector& ans, int z, int v, Union_Find& uf, vector& memo) { for (auto i = memo.begin(), e = memo.end(); i != e; ) { if (uf.same(*i, z)) { ans[*i] = v; i = memo.erase(i); e = memo.end(); } else { ++i; } } } int main() { int n, m, q; scanf("%d %d %d", &n, &m, &q); vector

e; for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); a--; b--; e.emplace_back(a, b); } vector

query; for (int i = 0; i < q; i++) { int c, d; scanf("%d %d", &c, &d); c--; d--; query.emplace_back(c, d); e.erase(find(e.begin(), e.end(), P(c, d))); } Union_Find uf(n); for (auto i = e.begin(), f = e.end(); i != f; ++i) { uf.Union((*i).first, (*i).second); } vector ans(n, -1); vector memo; for (int i = 1; i < n; i++) { if (!uf.same(0, i)) ans[i] = 0; memo.emplace_back(i); } for (int i = q - 1; i >= 0; i--) { int x = query[i].first, y = query[i].second; if (uf.same(x, y)) continue; if (uf.same(0, x)) setter(ans, y, i + 1, uf, memo); else if (uf.same(0, y)) setter(ans, x, i + 1, uf, memo); uf.Union(x, y); } for (int i = 1; i < n; i++) { printf("%d\n", ans[i]); } return 0; }