记录编号	74765	评测结果	AAAAAAATTT
题目名称	[USACO Open09] 捉迷藏	最终得分	70
用户昵称	赵寒烨	是否通过	未通过
代码语言	Pascal	运行时间	3.021 s
提交时间	2013-10-26 11:40:31	内存使用	0.54 MiB

var
  i,n,m,x,y:longint;
  a:array [1..50000] of record
    x,y:longint;
  end;
procedure bfs;
  type
    re=record
      node,step:longint;
    end;
  var
    front,rear,i,ans,ansi,maxx:longint;
    q:array [1..1000000] of re;
    v:array [1..20000] of boolean;
    t:re;
  begin
    front:=1;
    rear:=1;
    fillchar(v,sizeof(v),false);
    q[rear].node:=1;
    q[rear].step:=0;
    v[1]:=true;
    while front<=rear do begin
      t:=q[front];
      inc(front);
      for i:=1 to m do begin
        if (a[i].x=t.node)and(not v[a[i].y]) then begin
          inc(rear);
          q[rear].node:=a[i].y;
          q[rear].step:=t.step+1;
          v[a[i].y]:=true;
        end;
        if (a[i].y=t.node)and(not v[a[i].x]) then begin
          inc(rear);
          q[rear].node:=a[i].x;
          q[rear].step:=t.step+1;
          v[a[i].x]:=true;
        end;
      end;
    end;
    maxx:=0;
    for i:=1 to rear do
      if q[i].step>maxx then maxx:=q[i].step;
    ans:=0;
    ansi:=m;
    for i:=1 to rear do
      if q[i].step=maxx then begin
        if ansi>q[i].node then ansi:=q[i].node;
        inc(ans);
      end;
    writeln(ansi,' ',maxx,' ',ans);
  end;
begin
  assign(input,'hideseek.in');reset(input);
  assign(output,'hideseek.out');rewrite(output);
  readln(n,m);
  for i:=1 to m do readln(a[i].x,a[i].y);
  bfs;
  close(input);
  close(output);
end.