#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define ld long double #define EPS 0.0000000001 #define INF 1e9 #define LINF (ll)INF*INF #define MOD 1000000007 #define rep(i,n) for(int i=0;i<(n);i++) #define loop(i,a,n) for(int i=a;i<(n);i++) #define all(in) in.begin(),in.end() #define shosu(x) fixed< vi; typedef vector vs; typedef pair pii; typedef vector vp; int gcd(int a, int b){ if(b==0) return a; return gcd(b,a%b); } int lcm(int a, int b){ return a/gcd(a,b)*b; } //Quick Find Weighted //https://topcoder.g.hatena.ne.jp/iwiwi/20131226/1388062106 //O(NlogN) class UnionFind{ private: vector i2g; // i2g[i] := アイテム i の所属するグループの番号 vector > g2i; // g2i[g] := グループ g に所属するアイテムたち public: UnionFind(){}; UnionFind(int size){ i2g.resize(size); g2i.resize(size); for (int i = 0; i < size; i++) { // 最初はアイテム i はグループ i に所属 i2g[i] = i; g2i[i].assign(1, i); } } // アイテム ia の所属するグループとアイテム ib の所属するグループを 1 つにする // (ia と ib は違うグループに所属するものとする) void merge(int ia, int ib) { // ia の所属するグループが ib の所属するグループより小さくならないようにする if (g2i[i2g[ia]].size() < g2i[i2g[ib]].size()) { swap(ia, ib); } int ga = i2g[ia], gb = i2g[ib]; // グループ gb に所属する全てのアイテムをグループ ga に移す for (int i = 0; i < g2i[gb].size(); i++) i2g[g2i[gb][i]] = ga; g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end()); g2i[gb].clear(); } // アイテム id と同じグループに所属しているアイテムを取得 vector get_group(int id){ vector ret; id = i2g[id]; for(int i = 0; i < g2i[id].size(); i++)ret.push_back(g2i[id][i]); return ret; } // アイテム ia とアイテム ib は同じグループに所属しているか? bool same(int ia, int ib) { return i2g[ia] == i2g[ib]; } }; signed main(void) { int n,m,q; cin >> n >> m >> q; vp in(m),e(q); rep(i,m){ int a,b; cin >> a >> b; a--,b--; in[i] = pii(a,b); } map ma; rep(i,q){ int a,b; cin >> a >> b; a--,b--; e[i] = pii(a,b); ma[pii(a,b)]++; } vi ans(n,0); UnionFind uf(n); rep(i,m)if(ma.find(in[i]) == ma.end()){ int a = in[i].first; int b = in[i].second; if(uf.same(a,b))continue; if(uf.same(a,0)){ vi v = uf.get_group(b); rep(i,v.size())ans[v[i]] = -1; }else if(uf.same(b,0)){ vi v = uf.get_group(a); rep(i,v.size())ans[v[i]] = -1; } uf.merge(a,b); } for(int i = q-1; i >= 0; i--){ int a = e[i].first; int b = e[i].second; if(uf.same(a,b))continue; if(uf.same(a,0)){ vi v = uf.get_group(b); rep(j,v.size())ans[v[j]] = i+1; }else if(uf.same(b,0)){ vi v = uf.get_group(a); rep(j,v.size())ans[v[j]] = i+1; } uf.merge(a,b); } loop(i,1,n)cout << ans[i] << endl; }