传送门

---

将一组关系\((A,B)\)之间连一条边，那么显然如果图中存在环长为\(len\)的环，那么面具的种数一定是\(len\)的因数。

值得注意的是这里环的关系除了\(A \rightarrow B \rightarrow C \rightarrow D \rightarrow A\)类型以外，\(A \rightarrow B \rightarrow C \rightarrow D + A \rightarrow D\)也是一种环，而后者的环长为\(3 - 1 = 2\)，是两条路的路径之差。为了方便计算后面这种环，改变一下加边方式，对于一组关系\((A,B)\)从\(A\)向\(B\)连一条权值为\(1\)的边，从\(B\)往\(A\)连一条权值为\(-1\)的边，这样两种环都可以在图上表示出来。

找环的方法就是先抽出一棵DFS树，对于每一条非树边加进去出现的环计算贡献。

注意如果某一个环中存在\(\geq 2\)条非树边，可以不统计入答案：不妨证明有\(2\)条非树边的情况。设两条边是\(A \rightarrow B\)和\(C \rightarrow D\)，DFS树根为\(E\)，那么存在有两条非树边的环\(E \rightarrow D \rightarrow C \rightarrow B \rightarrow A \rightarrow E\)，且同时存在\(E \rightarrow D \rightarrow C \rightarrow E\)和\(E \rightarrow B \rightarrow A \rightarrow E\)。经过\(2\)条非树边的环的权值正是后两条经过一条非树边的环的权值和，而\(gcd(a,b) = gcd(a , a+b) = gcd(b , a + b)\)，所以在后两个环加入答案的情况下，\(E \rightarrow D \rightarrow C \rightarrow B \rightarrow A \rightarrow E\)在答案中没有意义的。

如果图中有环，那么最后的最大答案就是所有环长的\(gcd\)，最小答案就是\(gcd\)因子中\(\geq 3\)的最小的那个。

如果图中没有环，因为可以连边把所有连通块连起来，那么最大答案就是所有连通块中的最长链的权值之和，最小答案就是\(3\)。

注意如果图中没有环而最长链权值之和\(\leq 3\)是要输出\(-1\ -1\)而不是\(3\ 3\)的

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<ctime>

#include<algorithm>

#include<cstring>

#include<iomanip>

#include<queue>

#define INF 0x3f3f3f3f

//This code is written by Itst

using namespace std;

inline int read(){

	int a = 0;

	char c = getchar();

	while(!isdigit(c) && c != EOF)

		c = getchar();

	while(isdigit(c)){

		a = a * 10 + c - 48;

		c = getchar();

	}

	return a;

}

const int MAXN = 100007;

struct Edge{

	int end , upEd , w;

}Ed[MAXN * 20];

int head[MAXN] , dis[MAXN] , N , M , cntEd , ans , minN , maxN , sum;

bool vis[MAXN];

inline int gcd(int a , int b){

	if(!a || !b) return a + b;

	a = a < 0 ? -a : a; b = b < 0 ? -b : b;

	int r = a % b;

	while(r){a = b; b = r; r = a % b;}

	return b;

}

inline void addEd(int a , int b , int c){

	Ed[++cntEd] = (Edge){b , head[a] , c};

	head[a] = cntEd;

}

void dfs(int x){

	minN = min(minN , dis[x]); maxN = max(maxN , dis[x]);

	vis[x] = 1;

	for(int i = head[x] ; i ; i = Ed[i].upEd)

		if(!vis[Ed[i].end]){

			dis[Ed[i].end] = dis[x] + Ed[i].w;

			dfs(Ed[i].end);

		}

		else

			ans = gcd(ans , dis[x] - dis[Ed[i].end] + Ed[i].w);

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("in","r",stdin);

	//freopen("out","w",stdout);

#endif

	N = read(); M = read();

	for(int i = 1 ; i <= M ; ++i){

		int a = read() , b = read();

		addEd(a , b , 1); addEd(b , a , -1);

	}

	for(int i = 1 ; i <= N ; ++i)

		if(!vis[i]){

			minN = maxN = 0;

			dfs(i);

			sum += maxN - minN + 1;

		}

	if(!ans)

		if(sum >= 3) cout << sum << " 3";

		else cout << "-1 -1";

	else if(ans <= 2) cout << "-1 -1";

	else

		for(int j = 3 ; j <= ans ; ++j)

			if(ans % j == 0){

				cout << ans << ' ' << j;

				break;

			}

	return 0;

}