//O(H + W + N)じゃないので負けた気がするけど、union find解を実装します。 #include #include #define rep(i, n) for(i = 0; i < n; i++) using namespace std; struct UF { int par[200000]; UF() { for (int i = 0; i < 200000; i++) par[i] = i; } int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); } bool same(int x, int y) { return root(x) == root(y); } void merge(int x, int y) { x = root(x); y = root(y); par[x] = y; } }; int h, w, n; vector et[200000]; vector ec[200000]; UF uf; int parent[200000]; int color[200000]; void dfs(int p, int v) { parent[v] = p; for (int i = 0; i < et[v].size(); i++) { int nv = et[v][i]; if (nv == p) continue; color[nv] = ec[v][i]; dfs(v, nv); } } vector get_path(int v, int _root) { vector path; while (v != _root) { path.push_back(color[v]); v = parent[v]; } return path; } void print(vector ans) { cout << ans.size() << endl; for (int i = 0; i < ans.size(); i++) { cout << ans[i] + 1; if (i + 1 < ans.size()) cout << " "; } cout << endl; } signed main() { int i; cin >> h >> w >> n; rep(i, n) { int r, c; cin >> r >> c; r--; c--; if (uf.same(r, c + h)) { dfs(-1, c + h); vector ans = get_path(r, c + h); ans.push_back(i); print(ans); return 0; } else { uf.merge(r, c + h); et[r].push_back(c + h); et[c + h].push_back(r); ec[r].push_back(i); ec[c + h].push_back(i); } } cout << -1 << endl; return 0; }