记录编号	484561	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]假面舞会	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	0.068 s
提交时间	2018-01-25 13:55:06	内存使用	1.33 MiB

#pragma GCC optimize("-O2")
#include<bits/stdc++.h>
#define N 100011
#define MARICLE __attribute__((optimize("-O2")))
//#define getchar nc
using namespace std;
int b,n,m,f[N],nf[N],aa,bb,sum,sums,i,a,bbb,anfa,anfb,ans,tmax[N],tmin[N],len,us[N],usmax;
char c;
inline char nc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
MARICLE inline void read (int &x){
	c=getchar();
	for (;!('0'<=c && c<='9');c=getchar());
	for (x=0;('0'<=c && c<='9');) {
		x=x*10+c-'0';c=getchar();} 
}
MARICLE int gcd (int a,int b){
	return b?gcd(b,a%b):a;
}
//int Find(int x){
//	if (x==f[x]) return x;
//	int orz=Find(f[x]); nf[x]+=nf[f[x]]; f[x]=orz; return f[x];
//}
MARICLE inline int Find(int x)
{
    int top,j,next;
    top=x;
    while (top!=f[top]) top=f[top];
    while (top!=x) 
    {
        next=f[x]; f[x]=top;
        j=next;
        do
        {
            nf[x]+=nf[j];
            j=f[j];
        }while (f[j]!=j);
        x=next;
    }
    return top;
}
MARICLE int gg() {
	int ggg=sqrt(ans),llll=0;
	for (i=3;i<=ggg;i++)
	 if (ans%i==0) {
	 	llll=i;break;
	 }
	if (ans%2==0&&llll==0) llll=ans/2;
    if (llll==0)
	 printf("%d %d\n",ans,ans);
	else printf("%d %d\n",ans,llll);
}
MARICLE int main () {
	freopen("party2008.in","r",stdin);
	freopen("party2008.out","w",stdout);
	read(n); read(m);
	for (i=1;i<=n;i++) f[i]=i;
	for (i=1;i<=m;i++)
      {
       read(a); read(bbb);
      	anfa=Find(a);//getfather(a);
      	anfb=Find(bbb);//getfather(bbb);
		if (anfa==anfb) {
			if (nf[a]-nf[bbb]!=-1)  {
				if (ans==0) ans=nf[a]-nf[bbb]+1;
				else
				  ans=gcd(ans,nf[a]-nf[bbb]+1);
			}
		//	 ans=max(ans,nf[a]-nf[bbb]+1);
			
		}
	    if (anfa!=anfb) {
      		f[anfb]=anfa; nf[anfb]=nf[a]-nf[bbb]+1;
		  }
	  }
	  if (ans!=0) {
	  	if (ans<=2) {
	  		printf("-1 -1\n");
	  		return 0;
		  }
		else /* 
		printf("%d %d",ans,ans);*/
		gg();
	  }
	  if (ans==0) {
	  	for (i=1;i<=n;i++) Find(i);
	  	for (i=1;i<=n;i++)
	  	 {
	  	 	tmin[f[i]]=min(tmin[f[i]],nf[i]);
	  	 	tmax[f[i]]=max(tmax[f[i]],nf[i]);
	  	 	us[f[i]]=1;
		   }
		for (i=1;i<=n;i++)
		 if (us[i]==1){
		 	len=max(len,tmax[i]-tmin[i]+1);
		 	usmax+=tmax[i]-tmin[i]+1;
		  } 
		  len=max(len,3);
		  if (usmax<3) {printf("-1 -1\n");return 0;}
		  if (len<=usmax) printf("%d %d\n",usmax,3);
	  }
}