program lights;
const
  oo=10000000;
var
  q:array[0..oo] of longint;
  map:array[0..40] of longint;
  n,m,i,h,t,r1,r2:longint;
  step:array[0..oo] of longint;
  tt:longint;

begin
  assign(input,'lights.in');
  reset(input);
  assign(output,'lights.out');
  rewrite(output);

  readln(n,m);
  for i:=1 to n do
    map[i]:=1 shl (i-1);
  for i:=1 to m do
  begin
    readln(r1,r2);
    map[r1]:=map[r1]+(1 shl (r2-1));
    map[r2]:=map[r2]+(1 shl (r1-1));
  end;

  h:=0;
  t:=1;
  q[1]:=0;
  step[1]:=0;
  tt:=(1 shl n)-1;
  while h<>t do
  begin
    h:=h+1;
    if h>oo then h:=0;
    for i:=1 to n do
    begin
      t:=t+1;
      if t>oo then t:=0;
      q[t]:=q[h] xor map[i];
      step[t]:=step[h]+1;
      if q[t]=tt then
      begin
        writeln(step[t]);
        close(input);
        close(output);
        halt;
      end;
    end;
  end;

  close(input);
  close(output);
end.