题解

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool build_target(vector<int>& target, vector<pair<int, int>> neiber, int n){
target[0] = 0; target[1] = neiber[0].first; target[n-1] = neiber[0].second;
for(int i = 1; i < n - 1; i++){
if(target[i-1] != neiber[target[i]].first && target[i-1] != neiber[target[i]].second)
return false;
if(target[i+1] != -1){
if(target[i+1] != neiber[target[i]].first && target[i+1] != neiber[target[i]].second)
return false;
continue;
}
if(target[i-1] == neiber[target[i]].first){
target[i + 1] = neiber[target[i]].second;
}else{
target[i + 1] = neiber[target[i]].first;
}
}
if((target[0] == neiber[target[n-1]].first && target[n-2] == neiber[target[n-1]].second) ||
(target[0] == neiber[target[n-1]].second && target[n-2] == neiber[target[n-1]].first))
return true;
return false;
}

int test_P1053(){
int n;
cin >> n;
vector<int> target = vector<int>(n);
target[0] = 0;
vector<pair<int, int>> neiber;
for(int i = 0; i < n; i++){
int left, right;
cin >> left >> right;
target[i] = -1;
neiber.push_back(pair<int, int>(left-1, right-1));
}
bool flag = build_target(target, neiber, n);
if( !flag ) return -1;
vector<int> dist_1 = vector<int>(n);
vector<int> dist_2 = vector<int>(n);
for(int i = 0; i < n; i++){
dist_1[(target[i] - i + n) % n] ++;
dist_2[(target[i]-(n-i-1) + n) % n] ;
}
int ans = 0;
for(int i = 0; i < n; i)
ans = max(ans, max(dist_1[i], dist_2[i]));
return n - ans;
}

int main(){
int ans = test_P1053();
cout << ans << endl;
return 0;
}