uses crt;

var
aa,bb,cc,dd,ee,ff,e,h,y,x:longint;
edge:array[1..1000,1..1000] of longint;
n,color:array[1..10000] of longint;
begin
  assign(input,'DATA5.txt'); reset(input);
  assign(output,'OUT5.txt'); rewrite(output);
  for aa:= 1 to 5 do begin
      readln(e);
	  h:=0;
	  for bb:= 1 to 100 do n[bb]:=0;
	  for bb:= 1 to e do begin
	      readln(x,y);
          if x <> y then begin
		  inc(n[x]);
		  inc(n[y]);
		  edge[x,n[x]]:=y;
		  edge[y,n[y]]:=x;
          end;
		  if x > h then h:=x;
		  if y > h then h:=y;
	  end;
	  for bb:= 1 to h do begin
	      color[bb]:=1;
	  end;
	  x:=1;
	  for bb:= 1 to h do begin
	      for cc:= 1 to n[bb] do begin
		      if color[edge[bb,cc]] = color[bb] then begin
                 color[edge[bb,cc]]:=color[bb]+1;
				 if color[bb]+1 > x then x:= color[bb]+1; 
			  end;
		  end;
	  end;
	  if x < 5 then
	  writeln(x)
	  else writeln(0);
  end;
  readln;
  close(input);
  close(output);
end.