Description

从前有个包含n个点，m条边，无自环和重边的无向图。

对于两个没有直接连边的点u;v，你可以将它们合并。具体来说，你可以删除u;v及所有以它们作为端点的边，然后加入一个新点x，将它与所有在原图中与u或v有直接连边的点连边。

你需要判断是否能通过若干次合并操作使得原图成为一条链，如果能，你还需要求出这条链的最大长度

 

Input

从文件merge.in中读入数据。

第一行两个正整数n;m，表示图的点数和边数。

接下来m行，每行两个正整数u;v，表示u和v之间有一条无向边

Output

输出到文件merge.out中。

如果能通过若干次合并操作使得原图成为一条链，输出链的最大长度，否则输出-1

 

Sample Input

【样例1输入】5 41 22 33 43 5【样例2输入】4 61 22 31 33 42 41 4 

Sample Output

【样例1输出】3【样例2输出】-1 

 

Data Constraint

对于30%的数据，

对于70%的数据，

对于100%的数据，

 

题解

• 首先，我们可以发现，对于一个三元环是不可以合并的，因为合并只能选两个没有直接相连的点
• 对于一个长度大于3的奇环，最后合并一定也会合并出一个三元环
• 那这个图，就是一个二分图
• 先将二分图中的全部联通分量和每个点属于哪个联通分量求出来
• 这个可以用dfs实现
• 对于每一个连通分量都构造了一条链
• 而对于任意两条链
• 显然可以通过一 次合并操作将它们并成一条，长度为它们的长度之和
• 因此，答案就是所有连通块的直径之和
• 可以用bfs实现

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 struct edge { int to,from; }e[100005*2]; 7 int n,m,cnt,tot,bz[1005],ans[1005],last[1005],state[1005][2],visit[1005],head,tail,mx; 8 bool boo; 9 void insert(int x,int y) { e[++cnt].to=y; e[cnt].from=last[x]; last[x]=cnt; }10 int abs(int x) { return x<0?-x:x; }11 void dfs(int x,int k)12 {13     if (boo==1) return;14     bz[x]=k;15     for (int i=last[x];i;i=e[i].from)16     {17         if (boo==1) return;18         if (bz[e[i].to]==k)19         {20             boo=1;21             return;22         }23         if (bz[e[i].to]==-k) continue;24         dfs(e[i].to,-k);25     }26 }27 int bfs(int x)28 {29     memset(visit,0,sizeof(visit));30     memset(state,0,sizeof(state));31     head=0; tail=1; state[1][1]=x; visit[x]=1;32     int r=0;33     while (head