记录编号	69556	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]假面舞会	最终得分	100
用户昵称	GDFRWMY	是否通过	通过
代码语言	Pascal	运行时间	0.132 s
提交时间	2013-09-18 13:00:38	内存使用	23.91 MiB

  var
    a,d : array[1..100000]of longint;
    v : array[1..100000]of boolean;
    ef,et,ec : array[1..2000000]of longint;
    x,y,i,n,m,ans,tot,m1,m2,m3 : longint;
    procedure link(x,y,z: longint);
    begin
    inc(tot);
    ec[tot]:=z;
    et[tot]:=y;
    ef[tot]:=a[x];
    a[x]:=tot;
    end;

    function gcd(x,y:longint):longint;
    begin
    if y=0 then exit(x);if x=0 then exit(y);
    exit(gcd(y,x mod y));
    end;

    procedure dfs(x:longint);
    var i : longint;
    begin
    i:=a[x];
    v[x]:=true;
    if d[x]<m1 then m1:=d[x];
    if d[x]>m2 then m2:=d[x];

    while i<>0 do
    begin
    if not v[et[i]]then
    begin
    d[et[i]]:=d[x]+ec[i];dfs(et[i]);end
    else
    ans:=gcd(abs(d[et[i]]-(d[x]+ec[i])),ans);
    i:=ef[i];
    end;
    end;

    begin
    assign(input,'party2008.in');reset(input);
    assign(output,'party2008.out');rewrite(output);
    readln(n,m);
    for i:=1 to m do
    begin
    readln(x,y);
    link(x,y,1);link(y,x,-1);
    end;
    ans:=0;
    m3:=0;
    m1:=maxlongint;
    m2:=-maxlongint;
    for i:=1 to n do
    if not v[i]then
    begin
    dfs(i);
    m3:=m3+m2-m1+1;
    m1:=maxlongint;
    m2:=-maxlongint;end;
    if ans<>0 then
    begin
    if ans<3 then begin
    writeln('-1 -1');
    halt;end;
    for i:=3 to ans do
    if ans mod i=0 then break;
    writeln(ans,' ',i);
    end else
    if m3<3 then begin writeln('-1 -1');halt;
    end
    else writeln(m3,' ',3);
    close(input);
    close(output);
    end.