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

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 1000000
#define ll long long
using namespace std;
int m1[N/10+5],m2[N/10+5];
int n,m,vis[N/10+5],dep[N/10+5],zhan[N/10+5],head=0,e;
int tot=0,t[N/10+5],blg[N/10+5],dp=0,adj[N/10+5];
struct node
{
    int v,next,l;
} a[N*2+4];
int gcd(int x,int y){return y? gcd(y,x%y):x;}
inline int read()
{
    int sum=0,f=1;char x=getchar();
    while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
    while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}
    return sum;
}
inline void add(int u,int v,int l)
{
     a[++e].v=v;
     a[e].next=adj[u];adj[u]=e;
     a[e].l=l;
}
inline void dfs(int x,int depp)
{
     zhan[++head]=x;vis[x]=1;dep[x]=depp;blg[x]=dp;
     for(int i=adj[x];i!=-1;i=a[i].next)
     {
          int to=a[i].v;
          if(blg[to])
          {
              if(vis[to]&&zhan[head-1]!=to&&(depp+a[i].l-dep[to]))
                  t[++tot]=abs(depp+a[i].l-dep[to]);
              continue;   
          }       
          dfs(to,depp+a[i].l);
          vis[to]=0;head--;
     }
}
int sb()
{
    freopen("party2008.in","r",stdin);
    freopen("party2008.out","w",stdout);
    memset(adj,-1,sizeof(adj));
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
         x=read();y=read();
         add(x,y,1);
         add(y,x,-1);
    }
    for(int i=1;i<=n;i++)
        if(!blg[i])
        {
              dp++;
              dfs(i,1);
        }
    if(tot)
    {
         int ans=t[1];
         for(int i=2;i<=tot;i++)ans=gcd(ans,t[i]);
         if(ans<3)printf("-1 -1\n");
         else
               for(int i=3;i<=ans;i++)  
                  if(!(ans%i))
                  {
                     printf("%d %d\n",ans,i);
                      break;  
                  }
    }
    else
    {
          int ans=0;
          for(int i=1;i<=n;i++)m1[i]=1<<28;
          for(int i=1;i<=n;i++){
             m1[blg[i]]=min(m1[blg[i]],dep[i]);
             m2[blg[i]]=max(m2[blg[i]],dep[i]);
          }
          for(int i=1;i<=n;i++)
            if(m2[i]!=0)
               ans+=m2[i]-m1[i]+1;
          if(ans<3)printf("-1 -1\n");
          else printf("%d 3\n",ans);
    }
   // while(1); 
}
int sha=sb();
int main(){;}