#include using namespace std; #define DUMP(x) cerr << #x << "=" << x << endl #define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("< >(x) #define rep(i,n) for(int i=0;i<(int)(n);i++) #define REP(i,m,n) for (int i=m;i<(int)(n);i++) #define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h)) #define ALL(a) (a).begin(),(a).end() typedef long long ll; const int INF = 1e9; typedef pair PII; int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1}; class UnionFind { public: vector par, union_size; vector> group; // group[i] := 根iの集合に属する要素の一覧 UnionFind(int n) : par(n), union_size(n, 1), group(n) { for (int i=0; i(); } set& get_same_group(int x) { return group[find(x)]; } int find(int x) { return (par[x] == x ? x : par[x] = find(par[x])); } bool is_same(int x, int y) { return find(x) == find(y); } }; int main() { ios::sync_with_stdio(false); int N, M, Q; cin >> N >> M >> Q; UnionFind UF(N); set AS, BS; vector B; rep(i, M + Q) { int U, V; cin >> U >> V; U--, V--; (i < M ? AS : BS).emplace(U, V); if (i >= M) B.emplace_back(U, V); } for (auto e : AS) { if (!BS.count(e)) UF.merge(e.first, e.second); } vector ans(N); REP(i, 1, N) { ans[i] = (UF.is_same(0, i) ? -1 : 0); } UF.get_same_group(0) = set(); reverse(B.begin(), B.end()); rep(i, Q) { int s = B[i].first, t = B[i].second; if (UF.is_same(s, t)) continue; set g; if (UF.is_same(0, s)) g.swap(UF.get_same_group(t)); if (UF.is_same(0, t)) g.swap(UF.get_same_group(s)); UF.merge(s, t); for (auto u : g) { assert(ans[u] == 0); ans[u] = Q - i; } } REP(i, 1, N) cout << ans[i] << endl; }