题目链接。

发现题解区说大多都是直接说再连一条边权为 $-1$ 的边，在这里略微证明一下正确性。​

解析

首先发现若图中没有环，最大答案为所有联通块的最长链长度之和，最小答案为 $3$。

若存在环，则最大答案为所有环的 $gcd$​​。为了在可接受的时间内找到所有环，我们对于每一条边的 $u\to v$​​，从 $u$​​ 向 $v$​​ 连一条边权为 $1$​​ 的边，从 $v$​​ 向 $u$​​ 连一条边权为 $-1$​​ 的边。然后每一次都从任意一个未被搜索过的点开始搜，并记录每一个点的距离 $dis$​​，若走到一个已走过的点 $i$​​，就取 $d-di{s}_i$​​ 作为一个新找到的环的长度，这部分代码如下：

inline void dfs(int u,int d){
    if(dis[u]){
        ans=gcd(ans,abs(d-dis[u]));
        return;
    }
    dis[u]=d;vis[u]=1;
    mx=max(mx,dis[u]);mn=min(mn,dis[u]);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;dfs(v,d+e[i].w);
    }
}

				

					
				
				

					
				
				

					
				
				

					
				
			

接着我们观察下面这张图。

我们发现，当图中出现上图这个情况时，记 $a$​​ 为红色环的长度，$b$​​ 为蓝色部分的长度，$c$​​​ 为中间部分的长度。这时的两个环的长度分别为 $a$​​ 和 $a+b-c$​​，但是我们搜索时搜出来的长度可能是 $a$​​ 和 $c-b$​​​ 或 $a+b-c$ 和 $c-b$，即先搜完 $a$ 这个环，再从 $T$ 点以 $-1$ 的道路通过 $b$ 回到 $S$​​ 点。

也就是说，这个做法想要正确，需要有 $gcd(a,a+b-c)=gcd(a,|c-b|)$ 且 $gcd(a,a+b-c)=gcd(a+b-c,|c-b|)$​​。

先证明前者：

• 若 $b\ge c$​，有 $gcd(a,|c-b|)=gcd(a,b-c)=gcd(a,a+b-c)$​，显然正确
• 若 $b<c$​ ，有 $gcd(a,|c-b|)=gcd(a,c-b)=gcd(a,a+c-b)$​，换言之，我们需要证明 $gcd(a,a+b)=gcd(a,a-b),a>b$​。

证明：

记 $x=gcd(a,a-b)$，则 $x|a$ 且 $x|b$。

设 $a=mx$，$b=nx$，有 $m$ 与 $m-n$ 互质且 $m>n$，故 $gcd(a,a+b)=gcd(mx,(m+n)x)$。

若 $m+n$ 与 $m$ 不互质，有 $gcd(m+n,m)=gcd(n,m)\ne 1$。

可设 $t=gcd(m,n)$，有 $m=k_{1}t,n=k_{2}t,m-n=(k_1-k_2)t$​​，与 $m$ 与 $m-n$ 互质矛盾。

故 $m+n$​ 与 $m$​ 互质，即 $gcd(a,a+b)=x=gcd(a,a-b)$​​。

再证明后者：

• 若 $c\ge b$，有 $gcd(a+b-c,|c-b|)=gcd(a+b-c,c-b)=gcd(a+b-c,a)$。
• 若 $c<b$，有 $gcd(a+b-c,|c-b|)=gcd(a+b-c,b-c)=gcd(a+b-c,a+2b-2c)$，将 $a+b-c$ 和 $b-c$ 分别看作 $gcd(a,a+b)=gcd(a,a-b)$ 中的 $a$ 和 $b$​，由上得证。

同时我们又发现，除了上图的情况，其他的情况搜到的环的长度都是真是的或是可以化成上图情况的。

因此，建反向的边权为 $-1$ 的边的做法是正确的。求出最大答案后，最小答案显然为最大答案的最小的 $\ge 3$ 的因子，求出答案后再判断一下和 $3$​​ 的关系即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
int n,m;
struct node{
    int to,nxt,w;
}e[M];
int cnt,head[N];
inline void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].w=w;
    head[u]=cnt;
}
int dis[N],ans,ans2,mx,mn;
bool vis[N];
inline int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
inline void dfs(int u,int d){
    if(dis[u]){
        ans=gcd(ans,abs(d-dis[u]));
        return;
    }
    dis[u]=d;vis[u]=1;
    mx=max(mx,dis[u]);mn=min(mn,dis[u]);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;dfs(v,d+e[i].w);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        add(u,v,1);add(v,u,-1);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            mx=-1e9;mn=1e9;
            dfs(i,1);
            ans2+=mx-mn+1;//找最长链
        }
    }
    if(ans){//有环
        if(ans<3) printf("-1 -1\n");
        else for(int i=3;i<=ans;i++){
            if(!(ans%i)){
                printf("%d %d\n",ans,i);
                return 0;
            }
        }
    }
    else{//没环
        if(ans2<3) printf("-1 -1\n");
        else printf("%d 3\n",ans2);
    }
    return 0;
}