首先我们无法将三角形变成一条链，而一个奇环操作之后将减少两个点最后变成三角形，所以有奇环则无法变成一条链。

对于一个无奇环的图，它一定是一个二分图。我们考虑对于每一个联通子块，以一个点为根生成BFS树。由于是二分图，同一层的节点都在同一部，互相没有连边，所以可以全部缩在一起，这样我们可以得到以这个点为起点可以生成的最长链。

那么一个联通子块的最长链就是这个子块的直径。

所以最后的答案就是所有联通子块的直径和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3;
const int maxm=2e5;
struct Edge{int u,v,nxt;};
int n,m;
int hd[maxn+5],et;
Edge e[maxm+5];
int tot;
int dis[maxn+5];
int col[maxn+5];
int res[maxn+5];
queue<int> qu;
int ans;
inline void Adde(int u,int v){
    e[et].u=u,e[et].v=v,e[et].nxt=hd[u],hd[u]=et++;
}
void Bfs(int u){
    int v,tmp=0;
    memset(dis,-1,sizeof(dis));
    while(qu.size()) qu.pop();
    qu.push(u);
    dis[u]=0;
    while(qu.size()){
        u=qu.front();
        qu.pop();
        tmp=max(tmp,dis[u]);
        for(int i=hd[u];~i;i=e[i].nxt){
            v=e[i].v;
            if(~dis[v]) continue;
            dis[v]=dis[u]+1;
            if(~col[v]){
                if(col[v]==col[u]){
                    puts("-1");
                    exit(0);
                }
            }
            else col[v]=col[u]^1;
            qu.push(v);
        }
    }
    res[col[u]>>1]=max(res[col[u]>>1],tmp);
}
signed main(){
    int u,v;
    memset(hd,-1,sizeof(hd));
    memset(col,-1,sizeof(col));
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d",&u,&v);
        Adde(u,v),Adde(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!(~col[i])) col[i]=tot,tot+=2;
        Bfs(i);
    }
    for(int i=0;i<=(tot>>1);i++) ans+=res[i];
    printf("%d",ans);
    return 0;
}