/* -*- coding: utf-8 -*- * * 1647.cc: No.1647 Travel in Mitaru city 2 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_H = 100000; const int MAX_W = 100000; const int MAX_N = 100000; const int MAX_M = MAX_H + MAX_W; /* typedef */ typedef vector vi; typedef deque dqi; typedef pair pii; typedef map mpii; /* global variables */ int xs[MAX_N], ys[MAX_N], uxs[MAX_N], uys[MAX_N]; mpii pmap; vi nbrs[MAX_M]; int ps[MAX_M], ds[MAX_M], cis[MAX_M]; /* subroutines */ /* main */ int main() { int h, w, n; scanf("%d%d%d", &h, &w, &n); for (int i = 0; i < n; i++) { scanf("%d%d", xs + i, ys + i); uxs[i] = xs[i], uys[i] = ys[i]; pmap[pii(xs[i], ys[i])] = i; } sort(uxs, uxs + n); sort(uys, uys + n); int xn = unique(uxs, uxs + n) - uxs; int yn = unique(uys, uys + n) - uys; for (int i = 0; i < n; i++) { int xi = lower_bound(uxs, uxs + xn, xs[i]) - uxs; int yi = lower_bound(uys, uys + yn, ys[i]) - uys; nbrs[xi].push_back(xn + yi); nbrs[xn + yi].push_back(xi); } int m = xn + yn; memset(ds, -1, sizeof(ds)); for (int st = 0; st < m; st++) if (ds[st] < 0) { ps[st] = -1, ds[st] = 0; vi pts; pts.push_back(st); for (int u = st; u >= 0;) { vi &nbru = nbrs[u]; int up = ps[u]; if (cis[u] < nbru.size()) { int v = nbru[cis[u]++]; if (v != up) { if (ds[v] < 0) { ps[v] = u, ds[v] = ds[u] + 1; pts.push_back(v); u = v; } else if (ds[v] < ds[u]) { dqi q; for (int i = ds[v]; i <= ds[u]; i++) q.push_back(pts[i]); if (q.front() >= xn) { q.push_back(q.front()); q.pop_front(); } int k = q.size(); printf("%d\n", k); for (int i = 0; i < k; i++) { int q0 = q[i], q1 = q[(i + 1) % k]; int xi, yi; if (q0 < xn) xi = q0, yi = q1 - xn; else xi = q1, yi = q0 - xn; int pi = pmap[pii(uxs[xi], uys[yi])]; printf("%d%c", pi + 1, (i + 1 < k) ? ' ' : '\n'); } return 0; } } } else { pts.pop_back(); u = up; } } } puts("-1"); return 0; }