#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } struct UnionFind{ int sz; vector par; vector rank; UnionFind(int n) : sz(n) { par.resize(sz); rank.assign(sz, 0); for(int i = 0; i < sz; ++i){ par[i] = i; } } int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } bool same(int x, int y){ return find(x) == find(y); } bool unite(int x, int y){ x = find(x), y = find(y); if(x == y) return false; if(rank[x] < rank[y]) par[x] = y; else{ par[y] = x; if(rank[x] == rank[y]) ++rank[x]; } return true; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, Q; cin >> N >> M >> Q; vector A(M), B(M), C(Q), D(Q); for(int i = 0; i < M; ++i){ cin >> A[i] >> B[i]; --A[i], --B[i]; } set> destroy; for(int i = 0; i < Q; ++i){ cin >> C[i] >> D[i]; --C[i], --D[i]; destroy.emplace(minmax(C[i], D[i])); } vector remain(M); for(int i = 0; i < M; ++i){ remain[i] = destroy.find(minmax(A[i], B[i])) == destroy.end(); } vector lb(N, -1), ub(N, Q + 1); bool update = true; while(update){ update = false; UnionFind uf(N); for(int i = 0; i < M; ++i){ if(remain[i]) uf.unite(A[i], B[i]); } vector> querys(Q + 1); for(int i = 1; i < N; ++i){ if(ub[i] - lb[i] > 1){ querys[(lb[i] + ub[i]) / 2].emplace_back(i); } } for(int i : querys[Q]){ if(uf.same(0, i)) lb[i] = Q; else ub[i] = Q; update = true; } for(int q = Q - 1; q >= 0; --q){ uf.unite(C[q], D[q]); for(int i : querys[q]){ if(uf.same(0, i)) lb[i] = q; else ub[i] = q; update = true; } } } for(int i = 1; i < N; ++i){ cout << (lb[i] == Q ? -1 : lb[i] + 1) << '\n'; } return 0; }