记录编号	69559	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]设计路线	最终得分	100
用户昵称	GDFRWMY	是否通过	通过
代码语言	Pascal	运行时间	0.960 s
提交时间	2013-09-18 13:01:27	内存使用	78.75 MiB

var
a,b,c,d,e,i,j,m,n,q,num,rp:longint;
f:array[0..100000,-1..20,0..3] of int64;
ne,l,fa:array[0..1000000]of longint;
procedure fff(x,y:longint);
var
w,e,o1,o2:int64;
begin
f[x,i,0]:=1;
w:=fa[x];
while w<>0 do
begin
e:=l[w];
if e<>y then
begin
fff(e,x);
o1:=f[e,i,0]+f[e,i,1]; if (o1 mod q=0)and(o1>0) then o1:=q else o1:=o1 mod q;
o2:=f[e,i-1,0]+f[e,i-1,1]+f[e,i-1,2]; if (o2 mod q=0)and(o2>0) then o2:=q else o2:=o2 mod q;
f[x,i,2]:=f[x,i,2]*o2+f[x,i,1]*o1; if (f[x,i,2] mod q=0)and(f[x,i,2]>0) then f[x,i,2]:=q else f[x,i,2]:=f[x,i,2] mod q;
f[x,i,1]:=f[x,i,1]*o2+f[x,i,0]*o1; if (f[x,i,1] mod q=0)and(f[x,i,1]>0) then f[x,i,1]:=q else f[x,i,1]:=f[x,i,1] mod q;
f[x,i,0]:=f[x,i,0]*o2;   if (f[x,i,0] mod q=0)and(f[x,i,0]>0) then f[x,i,0]:=q else f[x,i,0]:=f[x,i,0] mod q;
end;
w:=ne[w];
end;
end;
begin
   assign(input,'design.in'); reset(input);
   assign(output,'design.out'); rewrite(output);
read(n,m,q);
if m<>n-1 then
begin
writeln(-1);
writeln(-1);
exit;
end;
for a:=1 to m do
begin
read(i,j);
inc(num);
l[num]:=j;
ne[num]:=fa[i];
fa[i]:=num;
inc(num);
l[num]:=i;
ne[num]:=fa[j];
fa[j]:=num;
end;
i:=0;
while rp=0 do
begin
fff(1,0);
if f[1,i,0]+f[1,i,1]+f[1,i,2]>0 then
begin
rp:=1;
writeln(i);
writeln((f[1,i,0]+f[1,i,1]+f[1,i,2]) mod q);
break;
end;
inc(i);
end;
close(input); close(output);
end.