状态: Unaccepted
测评机: Xeond[6]
得分: 70分
提交日期: 2012-2-20 8:55:00
有效耗时: 1859毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时172ms
测试结果3: 通过本测试点|有效耗时172ms
测试结果4: 测试结果错误.错误结果为:2 3
正确结果应为:-1 -1
测试结果5: 测试结果错误.错误结果为:2 3
正确结果应为:8 3
测试结果6: 测试结果错误.错误结果为:16 3
正确结果应为:8018 3
测试结果7: 通过本测试点|有效耗时172ms
测试结果8: 通过本测试点|有效耗时187ms
测试结果9: 通过本测试点|有效耗时563ms
测试结果10: 通过本测试点|有效耗时421ms
{$M 65536000}
type
node=record
a,b,z:longint;
end;
var
e:array[1..2000005] of node;
next:array[1..2000005] of longint;
head,d:array[1..100005] of longint;
v:array[1..1000005] of boolean;
i,j,ans,an,n,m,x,y,tmax,tmin:longint;
procedure add(x,y,c:longint);
begin
inc(j);
with e[j] do
begin
a:=x;
b:=y;
z:=c;
end;
next[j]:=head[x];
head[x]:=j
;
end;
function gcd(x,y:longint):longint;
begin
if y=0 then exit(x) else
exit(gcd(y,x mod y));
end;
procedure dfs(x:longint);
var
i,y:longint;
begin
v[x]:=false;
i:=head[x];
while i<>0 do
begin
y:=e[i].b;
if not v[y] then
ans:=gcd(abs(d[x]+e[i].z-d[y]),ans)
else
begin
d[y]:=d[x]+e[i].z;
dfs(y);
end;
i:=next[i];
end;
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
procedure tree(x:longint);
var
i,y:longint;
begin
v[x]:=false;
tmax:=max(tmax,d[x]);
tmin:=min(tmin,d[x]);
i:=head[x];
while i<>0 do
begin
y:=e[i].b;
if v[y] then
begin
d[y]:=d[x]+e[i].z;
tree(y);
end;
i:=next[i];
end;
end;
begin
readln(n,m);
j:=0;
for i:=1 to m do
begin
readln(x,y);
add(x,y,1);
add(y,x,-1);
end;
ans:=0;
fillchar(v,sizeof(v),true);
for i:=1 to n do
if v[i] then
begin
d[i]:=0;
dfs(i);
end;
if ans>0 then
begin
for i:=3 to ans do
if ans mod i=0 then break;
an:=i;
end else
begin
fillchar(v,sizeof(v),true);
for i:=1 to n do
if v[i] then
begin
tmax:=0;
tmin:=0;
d[i]:=0;
tree(i);
if tmax-tmin+1>ans then ans:=tmax-tmin+1;
end;
an:=3;
end;
if ans>0 then
write(ans,' ',an) else
write(-1,' ',-1);
end.