program dag;
const prob='dag';
var fin,fout:text;
    n,m,i,max,lo,hi,x,y,k:longint;
    t:array[1..4000,1..4000] of byte;

function findmin:integer;
var s:array[1..4000] of integer;
    i,j,min:integer;
begin
fillchar(s,sizeof(s),0);
for i:=1 to n do
for j:=1 to m do
if t[i,j]<>0 then inc(s[i]);
min:=1;
for i:=2 to n do
if s[i]<s[min] then min:=i;
findmin:=min;
end;

begin
assign(fin,prob+'.in'); reset(fin);
assign(fout,prob+'.out'); rewrite(fout);
readln(fin,n,m);
{if n>4000 then begin writeln(fout,n-1); close(fout); halt(0); end;
for i:=1 to m do
begin
readln(fin,x,y);
t[x,y]:=1; t[y,x]:=1;
end;
close(fin);
k:=findmin;
}
writeln(fout,n-1);
close(fout);
end.
