{$O-,Q+,R+}
uses SysUtils, Math;

const MaxN=300;
      MaxM=100000;

procedure readr (var x:integer; a, b:integer);
begin
  assert (not seekeoln); read (x); assert ((a<=x) and (x<=b));
end;

procedure readl;
begin
  assert (eoln); assert (not eof); readln
end;

var n, m, a, b, i, j, k:integer;
    g:array [1..MaxN, 1..MaxN] of integer;

begin
  reset (input, 'weakconn.in');
  rewrite (output, 'weakconn.out');
  readr (n, 2, MaxN);
  readr (m, 1, MaxM);
  readl;
  fillchar (g, sizeof (g), 63);
  for i:=1 to m do begin
    readr (a, 1, n); readr (b, 1, n); readl;
    assert (a<>b);
    g[a, b]:=min (g[a, b], 0);
    g[b, a]:=min (g[b, a], 1);
  end;
  assert (eof);
  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        g[i, j]:=min (g[i, j], g[i, k]+g[k, j]);
  m:=0; for i:=1 to n do for j:=1 to n do m:=max (m, g[i, j]);
  assert (m<=n-1);
  writeln (m);
end.