var
  n,m:longint;
  ans:int64;
  g:array[0..50,0..50]of longint;
  high:array[0..1000]of int64;
  q:array[0..5000000]of int64;
  b:array[0..5000000]of longint;
  f:Array[0..5000000]of boolean;

procedure init;
var
  i,x,y:longint;
begin
  assign(input,'lights.in'); reset(input);
  assign(output,'lights.out'); rewrite(output);
  readln(n,m);
  for i:=1 to m do
  begin
    readln(x,y);
    inc(g[x,0]);
    g[x,g[x,0]]:=y;
    inc(g[y,0]);
    g[y,g[y,0]]:=x;
  end;
  high[1]:=1;
  ans:=1;
  for i:=2 to n do
  begin
    high[i]:=high[i-1]*2;
    inc(ans,high[i]);
  end;
end;

procedure print(k:longint);
begin
  writeln(k);
  close(input);
  close(output);
  halt;
end;

procedure bfs;
var
  i,j,h,t,x,y:longint;
begin
  h:=1;
  t:=1;
  q[1]:=0;
  repeat
    x:=q[h];
    for i:=1 to n do
    begin
      y:=x;
      y:=y xor high[i];
      for j:=1 to g[i,0] do y:=y xor high[g[i,j]];
      if not f[y] then
      begin
        inc(t);
        b[t]:=b[h]+1;
        q[t]:=y;
        f[y]:=true;
        if y=ans then print(b[t]);
      end;
    end;
    inc(h);
  until h>t;
end;

begin
  init;
  bfs;
  close(input);
  close(output);
end.