#include #include using namespace std; using namespace atcoder; #define int long long using vec_int = vector; using vec_ii = vector; using vec_iii = vector; using vec_iiii = vector; using P = pair; using T = tuple; using ll = long long; using ld = long double; #define rep(i, n) for(int i = 0; i < (int)(n); i++) void cout_line(vector &a){ for(int i=0;i>H>>W>>N; vec_int x(N), y(N); rep(i,N)cin>>x.at(i)>>y.at(i); vector x_city(H+1); vector y_city(W+1); rep(i, N){ x_city.at(x.at(i)).push_back(i); y_city.at(y.at(i)).push_back(i); } vec_int visited(N+1, -2); queue que; for(int i=0;i visited_map; while(!que.empty()){ int pos, direc, prev; tie(pos, direc, prev) = que.front(); que.pop(); //cout<<"pos:"<=-1&&prev>=0){ pos1 = pos; pos2 = prev; flag = 1; break; } } visited_map[pos] = prev; if(direc==0){ for(auto next: x_city.at(x.at(pos))){ if(next==pos)continue; if(visited.at(next)>0)continue; que.emplace(next, 1, pos); } }else{ for(auto next: y_city.at(y.at(pos))){ if(next==pos)continue; if(visited.at(next)>0)continue; que.emplace(next, 0, pos); } } } if(flag==0){ for(auto temp:visited_map){ visited.at(temp.first) = 1; } continue; } vec_int route1, route2; while(pos1>=0){ route1.push_back(pos1); pos1 = visited_map[pos1]; } reverse(route1.begin(), route1.end()); while(pos2>=0){ route2.push_back(pos2); pos2 = visited_map[pos2]; } reverse(route2.begin(), route2.end()); int ind = 0; for(int i=0;i