#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
gp_hash_table<string,int>ht;
vector<int>cnt[(int)1e5+5];
int out[(int)1e5+5],sz[(int)1e5+5];
bool vis[(int)1e5+5];
set<pair<int,int>>se;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n,c=0,u,v,ans=0;
string s,t;
cin>>n;
if(n%2){
cout<<-1;
return 0;
}
for(int i=0;i<n;i++){
cin>>s>>t;
if(ht.find(s)!=ht.end())u=ht[s];
else u=ht[s]=c++;
if(ht.find(t)!=ht.end())v=ht[t];
else v=ht[t]=c++;
out[u]=v;
if(u==v)continue;
cnt[u].push_back(v),cnt[v].push_back(u);
sz[u]++,sz[v]++;
}
for(auto p:ht)cout<<p.first<<' '<<p.second<<'\n';
for(int i=0;i<n;i++){
if(out[out[i]]==i&&out[i]!=i&&!vis[i]){
ans+=2,vis[i]=vis[out[i]]=1;
for(int j:cnt[i])sz[j]--;
}
}
for(int i=0;i<n;i++)se.insert({sz[i],i});
while(se.size()){
auto p=*se.begin();
se.erase(se.begin());
if(p.first==0||vis[p.second])continue;
for(int i:cnt[p.second]){
if(!vis[i]){
vis[p.second]=vis[i]=1;
for(int j:cnt[p.second]){
if(!vis[j]){
se.erase({sz[j],j});
sz[j]--;
se.insert({sz[j],j});
}
}
for(int j:cnt[i]){
if(!vis[j]){
se.erase({sz[j],j});
sz[j]--;
se.insert({sz[j],j});
}
}
ans++;
break;
}
}
}
cout<<n-ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
146 ms |
33568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
