program count;
type pnod=^nod;
     nod=record
       val:longint;
       next:pnod;
     end;
var f:text;
    c:array[1..4000,1..4000] of boolean;
    vec:array[1..4000] of pnod;
    n,m,i,a,b:longint;
    p:pnod;

procedure rezolva4;
var i,cont:longint;
    p,q,r:pnod;
begin
  cont:=0;
  for i:=1 to n do begin
    p:=vec[i];
    while p<>nil do begin

      q:=vec[p^.val];
      while q<>nil do begin

        if c[i,q^.val] then begin
          r:=vec[q^.val];
          while r<>nil do begin
            if (c[r^.val,i]) and (c[r^.val,p^.val]) then inc(cont);
            r:=r^.next;
          end;
        end;

        q:=q^.next;
      end;

      p:=p^.next;
    end;
  end;
  if cont>0 then begin
     write(f,'4 ',cont);
     close(f);
     halt;
  end;
end;

procedure rezolva3;
var i,cont:longint;
    p,q:pnod;
begin
  cont:=0;
  for i:=1 to n do begin
    p:=vec[i];
    while p<>nil do begin

      q:=vec[p^.val];
      while q<>nil do begin

        if c[i,q^.val] then inc(cont);

        q:=q^.next;
      end;

      p:=p^.next;
    end;
  end;
  if cont>0 then begin
     write(f,'3 ',cont);
     close(f);
     halt;
  end;
end;

procedure rezolva2;
var i,cont:longint;
    p:pnod;
begin
  cont:=0;
  for i:=1 to n do begin
    p:=vec[i];
    while p<>nil do begin

      inc(cont);

      p:=p^.next;
    end;
  end;
  if cont>0 then begin
     write(f,'2 ',cont);
     close(f);
     halt;
  end;
end;

begin
  assign(f,'count.in');reset(f);
    readln(f,n,m);
    for i:=1 to m do begin
      readln(f,a,b);
      c[a,b]:=true;c[b,a]:=true;
      if a>b then begin
        a:=a xor b; b:=a xor b; a:=a xor b;
      end;
      if vec[a]=nil then begin
        new(p);p^.next:=nil;
        p^.val:=b;vec[a]:=p;
      end else begin
        new(p);p^.next:=vec[a];
        p^.val:=b;vec[a]:=p;
      end;
    end;
  close(f);
  assign(f,'count.out');rewrite(f);
    rezolva4;
    rezolva3;
    rezolva2;
    write(f,'1 ',n);
  close(f);
end.