var
 line:array[1..2500] of record x,y:integer; end;
 d,c:array[1..50] of integer;
 path:array[1..2500] of integer;
 a,b:array[1..50,1..50] of integer;
 use:array[1..2500] of boolean;
 i,j,n,m:integer;

Function Gcd(a,b:integer):integer;
begin
 if a mod b=0 then Gcd:=b else
  Gcd:=Gcd(b,a mod b);
end;

Function OK(k:integer):boolean;
var i,j:integer;
begin
 OK:=true; if (d[k]<=1) then exit;
 j:=a[k,1];
 for i:=2 to d[k] do
  begin
   j:=GCD(j,b[k,a[k,i]]);
   if j=1 then exit;
  end;
 OK:=false;
end;

Procedure Print;
begin
 writeln('YES');
 for i:=1 to m-1 do write(path[i],' '); writeln(path[m]);
 halt;
end;

Procedure Get(k:integer);
var i:integer;
begin
if k=m+1 then
  Print;
 for i:=1 to m do if use[i] then
  begin
   path[k]:=i; use[i]:=false;
   b[line[k].x,line[k].y]:=i;
   b[line[k].y,line[k].x]:=i;
   inc(c[line[k].x]); inc(c[line[k].y]);
   if c[line[k].x]=d[line[k].x]
    then
     if OK(line[k].x)
      then
       if c[line[k].y]=d[line[k].y]
        then
         if OK(line[k].y) then Get(k+1)
                          else
        else Get(k+1)
      else
    else
   if c[line[k].y]=d[line[k].y]
    then
     if OK(line[k].y) then Get(k+1)
                      else
   else Get(k+1);
   use[i]:=true;
   dec(c[line[k].x]); dec(c[line[k].y]);
  end;
end;

begin
// assign(input,'1040.in'); reset(input);
 readln(n,m); fillchar(d,sizeof(d),0);
 for i:=1 to m do
  begin
   readln(line[i].x,line[i].y);
   inc(d[line[i].x]); inc(d[line[i].y]);
   a[line[i].x,d[line[i].x]]:=line[i].y;
   a[line[i].y,d[line[i].y]]:=line[i].x;
  end;
 fillchar(use,sizeof(use),true);
 fillchar(c,sizeof(c),0);
 Get(1);
 writeln('NO');
end.