//行: 0~h-1, 列:0~w-1で頂点を持つ一般的なテク. 閉路検出. #include #include #include #include #include #define rep(i, n) for(i = 0; i < n; i++) using namespace std; typedef pair P; int h, w, n; vector et[200000]; //行き先 vector visit; map toId; bool dfs(int pv, int v, stack &path) { visit[v] = true; path.push(v); for (int i = 0; i < et[v].size(); i++) { int nv = et[v][i]; if (pv == nv) continue; if (visit[nv]) { if (path.size() >= 4) { return true; } continue; } else { if (dfs(v, nv, path)) return true; } } visit[v] = false; path.pop(); return false; } vector makeAnswer(stack path) { vector vs; while (!path.empty()) { int v = path.top(); path.pop(); vs.push_back(v); } int l = 0, r = vs.size() - 1; while (l < r) { swap(vs[l], vs[r]); l++; r--; } vector ans; for (int i = 0; i < vs.size(); i++) { int r, c; if (i + 1 == vs.size()) { if (vs[i] < h) { r = vs[i]; c = vs[0] - h; } else { c = vs[i] - h; r = vs[0]; } } else { if (vs[i] < h) { r = vs[i]; c = vs[i + 1] - h; } else { c = vs[i] - h; r = vs[i + 1]; } } int id = toId[P(r, c)]; ans.push_back(id); } return ans; } void printAnswer(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--; et[r].push_back(c + w); et[c + h].push_back(r); toId[P(r, c)] = i; } visit = vector(h + w, false); stack path; rep(i, h) { if (visit[i]) continue; if (dfs(-1, i, path)) { vector ans = makeAnswer(path); printAnswer(ans); return 0; } } cout << -1 << endl; return 0; }