传送门: https://ac.nowcoder.com/acm/contest/3274/B
牛客练习赛题，真就特判猜结论呗
// 他没说有好几个连通块啊
1 有环（所有点度数为2），极限就是n（连通块的定点数）
2 有链子，或者单点(度数不可能大于2,)
3 特判四个顶点的菊花图。。。。输出3
4否则全是-1
我服了。。。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#define maxn 101011
using namespace std;
int de[maxn];
vector<int>G[maxn];
void insert(int be,int en){
G[be].push_back(en);
}
int cnt[10];
int an=0;
int vis[maxn];
int dfs(int x){
if(vis[x]) return 0;
vis[x] = 1;
if(de[x] == 0) cnt[0]++;
else if(de[x] == 1) cnt[1] ++;
else if(de[x] == 2) cnt[2]++;
else if(de[x] == 3) cnt[3]++;
else if(de[x] > 3) cnt[4] ++;
an++;
for(int i=0;i<G[x].size();i++){
int p = G[x][i];
dfs(p);
}
return 0;
}
int main(){
int n,m;
int be,en;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&be,&en);
insert(be,en);
insert(en,be);
de[be]++;
de[en]++;
}
int ans=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
an=0;
for(int k=0;k<5;k++) cnt[k] = 0;
dfs(i);
if(cnt[4]){
printf("-1\n");
return 0;
}
if(cnt[2] && cnt[1] == 0 && cnt[3] == 0){
ans += an;
}
else if(an == 4 && cnt[3] == 1 && cnt[1] == 3){
ans += 3;
}
else if(cnt[3] == 0 && cnt[1] == 2 && cnt[2]){
}
else if(cnt[0]){
}
else{
printf("-1\n");
return 0;
}
}
}
printf("%d\n",ans);
return 0;
}