Beyond the Void

/* 
 * Problem: NOI2008 party
 * Author: Guo Jiabao
 * Time: 2009.3.4 22:41
 * State: Solved
 * Memo: dfs找环和链 求公约数
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=100001,MAXM=1000001;
using namespace std;
struct edge
{
	edge *next,*op;
	int t,c;
	bool nuked;
}ES[MAXM];
struct vertex
{
	edge *f,*l;
	int it,bl;
	bool vis;
}V[MAXN];
int N,M,EC,Ccnt,Gans,Mans,D;
int C[MAXN],BMax[MAXN],BMin[MAXN];
inline edge * addedge(int a,int b,int c)
{
	if (V[a].l)
		V[a].l=V[a].l->next=&ES[++EC];
	else
		V[a].f=V[a].l=&ES[++EC];
	ES[EC].t=b;
	ES[EC].c=c;
	ES[EC].nuked=false;
	return &ES[EC];
}
void init()
{
	int i,a,b;
	freopen("party2008.in","r",stdin);
	freopen("party2008.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		edge *e1=addedge(a,b,1);
		edge *e2=addedge(b,a,-1);
		e1->op=e2;
		e2->op=e1;
	}
	Gans=0;
}
inline int ABS(int a) {return a<0?-a:a;}
void findcircle(int u,int it)
{
	V[u].it=it;
	V[u].vis=true;
	for (edge *k=V[u].f;k;k=k->next)
	{
		if (k->nuked) continue;
		k->nuked=k->op->nuked=true;
		int v=k->t;
		if (!V[v].vis)
			findcircle(v,it+k->c);
		else
		{
			if (it+k->c - V[v].it!=0)
				C[++Ccnt]=ABS(it+k->c - V[v].it);
		}
	}
}
inline int gcd(int a,int b)
{
	int c;
	while (b)
	{
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}
void findpart(int u)
{
	V[u].bl=D;
	for (edge *k=V[u].f;k;k=k->next)
	{
		int v=k->t;
		if (V[v].bl==0)
			findpart(v);
	}
}
void part() //求连通分量
{
	int i;
	D=0;
	for (i=1;i<=N;i++)
		V[i].bl=0;
	for (i=1;i<=N;i++)
	{
		if (V[i].bl==0)
		{
			++D;
			findpart(i);
			BMin[D]=0x7FFFFFFF;
			BMax[D]=-0x7FFFFFFF;
		}
	}
}
void furthest(int u,int it)
{
	V[u].it=it;
	V[u].vis=true;
	for (edge *k=V[u].f;k;k=k->next)
	{
		if (k->nuked) continue;
		k->nuked=k->op->nuked=true;
		int v=k->t;
		furthest(v,it+k->c);
	}
}
void link()
{
	int i;
	for (i=1;i<=N;i++)
	{
		V[i].vis=false;
		for (edge *k=V[i].f;k;k=k->next)
			k->nuked=k->op->nuked=false;
	}
	for (i=1;i<=N;i++)
	{
		if (!V[i].vis)
			furthest(i,1);
		if (V[i].it>BMax[ V[i].bl ])
			BMax[ V[i].bl ]=V[i].it;
		if (V[i].it<BMin[ V[i].bl ])
			BMin[ V[i].bl ]=V[i].it;
	}
	Gans=0;
	for (i=1;i<=D;i++)
		Gans+=BMax[i]-BMin[i]+1;
	if (Gans < 3)
		Gans=Mans=-1;
	else
		Mans=3;
}
void solve()
{
	int i,GCD,LCD,MIN;
	for (i=1;i<=N;i++)
		if (!V[i].vis)
			findcircle(i,1);
	MIN=GCD=C[1];
	for (i=2;i<=Ccnt;i++)
	{
		GCD=gcd(GCD,C[i]);
		if (C[i] < MIN)
			MIN = C[i];
	}
	for (LCD=3;LCD<=MIN;LCD++)
	{
		for (i=1;i<=Ccnt;i++)
			if (C[i] % LCD !=0)
				break;
		if (i>Ccnt)
			break;
	}
	if (Ccnt==0) //无环
	{
		part();
		link();
	}
	else if (GCD>=3)
	{
		Gans=GCD;
		Mans=LCD;
	}
	else
		Gans=Mans=-1;
}
int main()
{
	init();
	solve();
	printf("%d %dn",Gans,Mans);
	return 0;
}