#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 #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair P; struct unionfind{ vector par, sz; unionfind() {} unionfind(int n):par(n), sz(n, 1){ for(int i=0; isz[y]) swap(x, y); par[x]=y; sz[y]+=sz[x]; } bool same(int x, int y){ return find(x)==find(y); } int size(int x){ return sz[find(x)]; } }; int main() { int h, w, n; cin>>h>>w>>n; int x[100010], y[100010]; int n1=100000; vector

g[200020]; unionfind uf(2*n1); vector ans; int par[200020]; auto dfs=[&](auto dfs, int x, int p)->void{ for(auto q:g[x]){ if(q.first==p){ par[x]=q.second; }else{ dfs(dfs, q.first, x); } } }; for(int i=0; i>x[i]>>y[i]; x[i]--; y[i]--; if(uf.same(x[i], y[i]+n1)){ dfs(dfs, y[i]+n1, -1); int v=x[i]; while(v!=y[i]+n1){ ans.push_back(par[v]); if(v