#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=22;
int a[N],vis[N],ssz[N],sz[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
map<string,int>m;
int d=1;
for(int i=0;i<n;i++){
string u,v; cin>>u>>v;
if(!m[u]) m[u]=d++;
if(!m[v]) m[v]=d++;
a[m[u]-1]=m[v]-1;
ssz[m[v]-1]++;
}
if(n%2) { cout<<-1; return 0; }
int ans=1e18;
for(int i=0;i<(1<<n);i++){
memset(vis,0,sizeof vis);
int ss=0;
bool f=true;
for(int i=0;i<n;i++) sz[i]=ssz[i];
for(int j=0;j<n;j++){
if((i>>j)&1) vis[j]=1,sz[a[j]]--,ss++;
else if(a[j]==j) f=false;
}
if(!f) continue;
queue<int>q;
int g=0;
for(int i=0;i<n;i++){
if(!vis[i]&&sz[i]==0) q.push(i);
if(a[a[i]]==i&&a[i]!=i) g++;
}
while(q.size()){
int x=q.front(); q.pop();
if(!vis[x]&&!sz[x]){
if(!vis[a[x]]){
vis[x]=1; vis[a[x]]=1;
sz[a[a[x]]]--;
if(!vis[a[a[x]]]) q.push(a[a[x]]);
}
}
}
for(int i=0;i<n;i++){
if(!vis[i]){
int s=1,j=i; vis[i]=1;
while(!vis[a[j]]) j=a[j],s++,vis[j]=1;
if(s%2) f=false;
}
}
if(!f) continue;
ans=min(ans,ss+(n-ss)/2-g/2);
}
if(ans==1e18) cout<<-1;
else cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |