记录编号	528268	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]假面舞会	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.253 s
提交时间	2019-03-04 09:41:19	内存使用	16.43 MiB

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<queue>
#define maxn 100010
#define INF 1000000000
using namespace std;
vector<pair<int,int> >c[maxn];
int n,m,f[maxn],li=0,de=0,sh=INF,tr=0;
bool circle=0,v[maxn];
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
void DFS(int x,int d){
	if(v[x])return;
	v[x]=1;f[x]=d;
	de=max(de,d);
	sh=min(sh,d);
	int i,now;
	for(i=0;i<c[x].size();i++){
		now=c[x][i].first;
		if(!v[now])DFS(now,d+c[x][i].second);
		else{
			int temp=abs(d+c[x][i].second-f[now]);
			if(temp){
				circle=1;
				li=gcd(li,temp);
			}
		}
	}
	return;
}
int limited_fac(int x){
	int ans=INF,high=(int)sqrt((double)x);
	for(int i=1;i<=high;i++){
		if(x%i==0){
			if(i>=3)ans=min(ans,i);
			ans=min(ans,x/i);
		}
	}
	return ans;
}
int main(){
	freopen("party2008.in","r",stdin);
	freopen("party2008.out","w",stdout);
	scanf("%d%d",&n,&m);
	int a,b;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(make_pair(b,1));
		c[b].push_back(make_pair(a,-1));
	}
	for(int i=1;i<=n;i++){
		if(v[i])continue;
		de=0;sh=INF;
		DFS(i,0);
		tr+=(de-sh+1);
	}
	if(!circle){
		if(tr<3)printf("-1 -1\n");
		else printf("%d 3\n",tr);
	}
	else{
		if(li<3)printf("-1 -1\n");
		else printf("%d %d\n",li,limited_fac(li));
	}
	return 0;
}