#include #define rep(i,n) for(int i=0;i<(int)(n);i++) #define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++) #define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++) #define setp(n) fixed << setprecision(n) template bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } #define ll long long #define vll vector #define vi vector #define pll pair #define pi pair #define all(a) (a.begin()),(a.end()) #define rall(a) (a.rbegin()),(a.rend()) #define fi first #define se second #define pb push_back #define ins insert #define debug(a) cerr<<(a)< ostream &operator<<(ostream &os, const pair &p){return os<<"("< istream &operator>>(istream &is, pair &p){return is>>p.fi>>p.se;} template vector make_vec(size_t a){ return vector(a); } template auto make_vec(size_t a, Ts... ts){ return vector(ts...))>(a, make_vec(ts...)); } //------------------------------------------------- //--Graph Template //------------------------------------------------- template struct Graph { vector > adj; Graph(int N):adj(N){} virtual void add_edge(int v, E e){adj[v].push_back(e);} vector& operator[](int v){return adj[v];} inline int size(){return adj.size();} }; namespace graph { struct SimpleEdge { int to; SimpleEdge(int to):to(to){} }; } struct UWGraph : public Graph { UWGraph(int N):Graph(N){} void add_edge(int v, int e){adj[v].push_back({e});} }; //------------------------------------------------- //--Get Cycle Any //------------------------------------------------- namespace Cycle { stack st; vector seen,finished; int pos; template void dfs(int v, int p, Graph &G, bool dir=true){ st.push(v); seen[v] = true; for(auto &e:G[v]){ if (!dir && e.to==p) continue; if (finished[e.to]) continue; if (seen[e.to] && !finished[e.to]){ pos = e.to; return; } dfs(e.to,v,G,dir); if (pos!=-1) return; } finished[v] = true; st.pop(); } void init(int V){ pos = -1; st=stack(); seen.resize(V,false); finished.resize(V,false); } vector restore(){ vector ret; if (pos==-1) return ret; while(!st.empty()){ int u = st.top(); st.pop(); ret.push_back(u); if (u==pos) break; } reverse(ret.begin(),ret.end()); return ret; } template vector get(Graph &G, bool dir=true){ int V = G.size(); init(V); for(int i=0;i vector get(int v, Graph &G, bool dir=true){ int V = G.size(); init(V); dfs(v,-1,G,dir); return restore(); } template vector minimize(vector &cycle, Graph &G, bool dir=true){ vector ret; int L = cycle.size(); if (L==0) return ret; unordered_map Mp; for(int j=0;j>H>>W>>N; vector row(H), col(W); rep(i,N){ int y,x; cin>>y>>x; y--; x--; row[y].pb(i); col[x].pb(i); } UWGraph G(4*N); rep(i,H){ auto &vec = row[i]; int sz = vec.size(); rep(j,sz-1){ int from = vec[j]; int to = vec[j+1]; G.add_edge(from,to); } rep(j,sz-1){ int from = vec[j+1] + N; int to = vec[j] + N; G.add_edge(from,to); } rep(j,sz-1){ int from = vec[j] + 2*N; int to = vec[j+1]; G.add_edge(from,to); from = vec[j] + 3*N; G.add_edge(from,to); } rep(j,sz-1){ int from = vec[j+1] + 2*N; int to = vec[j] + N; G.add_edge(from,to); from = vec[j+1] + 3*N; G.add_edge(from,to); } } rep(i,W){ auto &vec = col[i]; int sz = vec.size(); rep(j,sz-1){ int from = vec[j] + 2*N; int to = vec[j+1] + 2*N; G.add_edge(from,to); } rep(j,sz-1){ int from = vec[j+1] + 3*N; int to = vec[j] + 3*N; G.add_edge(from,to); } rep(j,sz-1){ int from = vec[j]; int to = vec[j+1] + 2*N; G.add_edge(from,to); from = vec[j] + N; G.add_edge(from,to); } rep(j,sz-1){ int from = vec[j+1]; int to = vec[j] + 3*N; G.add_edge(from,to); from = vec[j+1] + N; G.add_edge(from,to); } } auto cycle = Cycle::get(G); if (cycle.empty()){ cout<<"-1\n"; }else{ int sz = cycle.size(); cout<