记录编号	329814	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]假面舞会	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.222 s
提交时间	2016-10-25 18:59:57	内存使用	44.48 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2000010;
struct edge{int f,t,l;}w[N];
int n,m,ans,head[N],next[N],tail[N];
int abs(int x){return x>0?x:-x;}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void add(int f,int num){
	if (!head[f]) head[f]=tail[f]=num;
		else tail[f]=next[tail[f]]=num;
}
bool vis[N];int h[N],hmin,hmax,treeans;
void dfs(int x){
	if (vis[x]) return;
	vis[x]=1;
	hmin=min(hmin,h[x]);
	hmax=max(hmax,h[x]);
	for (int i=head[x];i;i=next[i])
	if (!vis[w[i].t]){
		h[w[i].t]=h[x]+w[i].l;
		dfs(w[i].t);
	}
	else ans=gcd(ans,abs(h[w[i].t]-h[x]-w[i].l));
}
int main()
{
	freopen("party2008.in","r",stdin);
	freopen("party2008.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&w[i].f,&w[i].t);
		w[i+m]=w[i];
		swap(w[i+m].f,w[i+m].t);
		w[i].l=1;w[i+m].l=-1;
		add(w[i].f,i);add(w[i].t,i+m);
	}
	for (int i=1;i<=n;i++)
	if (!vis[i]){
		hmin=hmax=0;dfs(i);
		treeans+=hmax-hmin+1;
	}
	if (!ans){
		if (treeans>=3) printf("%d 3\n",treeans);
			else puts("-1 -1");
	}
	else{
		int Min=-1;
		for (int i=3;i<=ans;i++)
		if (!(ans%i)){Min=i;break;}
		if (Min==-1) puts("-1 -1");
			else printf("%d %d\n",ans,Min);
	}
	return 0;
}