bzoj1064: [Noi2008]假面舞会

传送门：http://blog.sina.com.cn/s/blog_86942b1401015r81.html

 

const int N = 100010, M = 1000010;
struct Edge {
	int V, Val;
	Edge *Next;
	Edge() {}
	Edge(int _V, int _Val, Edge *_Next) : V(_V), Val(_Val), Next(_Next) {}
} *Fir[N];
int n, m;
int Dep[N];
bool Vis[N];
vector<int> C;

inline void Input() {
	scanf("%d%d", &n, &m);
	Rep(i, m) {
		int x, y;
		scanf("%d%d", &x, &y);
		Fir[x] = new Edge(y, 1, Fir[x]), Fir[y] = new Edge(x, -1, Fir[y]);
	}
}

inline int Gcd(int a, int b) {
	return b ? Gcd(b, a % b) : a;
}

int Depth_Max, Depth_Min, Depth;
queue<int> Q;
inline void Bfs(int S) {
	for(Q.push(S), Dep[S] = 0; sz(Q); Q.pop()) {
		int u = Q.front(), v;
		int dep = Dep[u];
		Depth_Max = max(Depth_Max, dep), Depth_Min = min(Depth_Min, dep);
		for(Edge *Tab = Fir[u]; Tab != NULL; Tab = Tab->Next)
			if(!Vis[v = Tab->V]) Q.push(v), Dep[v] = dep + Tab->Val, Vis[v] = 1;
			else if((dep + Tab->Val - Dep[v]) ^ 0) C.pub(abs(dep + Tab->Val - Dep[v]));
	}
}

inline void Solve() {
	clr(Vis, 0), C.clear(), Depth = 0;
	For(i, 1, n)
		if(!Vis[i]) {
			Depth_Max = -INF, Depth_Min = INF;
			Bfs(i);
			Depth += Depth_Max - Depth_Min + 1;
		}
	
	int Max = -INF, Min = INF;
	if(sz(C)) {
		FU(it, C)
			if(Max < 0) Max = *it;
			else Max = Gcd(Max, *it);
		For(i, 1, (int)(sqrt(Max)) + 1)
			if(Max % i == 0) {
				if(i > 2) Min = min(Min, i);
				if(Max / i > 2) Min = min(Min, Max / i);
			}
		if(Min < 3 || Max < 3) printf("-1 -1\n");
		else printf("%d %d\n", Max, Min);
	} else {
		if(Depth < 3) printf("-1 -1\n");
		else printf("%d 3\n", Depth);
	}
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1064");
	#endif
	Input();
	Solve();
	return 0;
}