记录编号	423547	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]假面舞会	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2017-07-12 08:22:01	内存使用	6.34 MiB

#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 1000005
#define Max(x,y) (x)>(y)? (x):(y)
#define Min(x,y) (x)<(y)? (x):(y)
int first[MAXN],e=1,Gcd,maxn,minn,n,m,final_ans,f[MAXN];
bool vis[MAXN];


inline int read(){
    int x=0;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
    return x;
}

int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}

struct edge{
    int u,v,next,w;
}a[MAXM<<1];

void push(int u,int v,int w){
    a[e].u=u;
    a[e].v=v;
    a[e].w=w;
    a[e].next=first[u];
    first[u]=e++;
}

void dfs(int u){
    vis[u]=1;
    maxn=Max(f[u],maxn);
    minn=Min(f[u],minn);
    for(int i=first[u];i;i=a[i].next){
        int v = a[i].v;
        if(!vis[v])
            f[v]=f[u]+a[i].w,dfs(v);
        else Gcd=gcd(Gcd,abs(f[u]-f[v]+a[i].w)),maxn=Max(f[v],maxn),minn=Min(f[v],minn);
    }
}

int lc(){
    freopen("party2008.in","r",stdin);

    FILE *fout;
    fout=fopen("party2008.out","wb");
    
    n=read();m=read();
    
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        push(u,v,1);push(v,u,-1);
    }
    
    for(int i=1;i<=n;i++)if(!vis[i]){
        minn=maxn=0;
        dfs(i);
        final_ans += maxn-minn+1;
    }
    
    if(!Gcd){
        if(final_ans<3){
            fprintf(fout,"-1 -1\n");
            return 0;
        }
        else fprintf(fout,"%d 3\n",final_ans);
        return 0;
    }
    
    else{
        int ans;
        for(ans=3;ans<Gcd&&Gcd%ans!=0;ans++);
        if(Gcd<3){
            fprintf(fout,"-1 -1\n");
            return 0;
        }
        fprintf(fout,"%d %d\n",Gcd,ans);
        return 0;
    }
    
    return 0;
}

int my_son=lc();

int main(){
}