I think of "N<=50" as "N,M<=50". Actually M<=N*(N-1)/2. It's a stupid mistake but it took me so much time to check out TAT
(btw, the point to solve the question is GCD(x,x+1)=1, it can be proved that the answer is always "YES".

When I make my algo work for not connected graphs, i got AC.
(I changed
   dfs(0)
 to
   for(int i=0;i<n;++i)if(!lev[i])dfs(i);
)

This problem is from IMO 1991 (problem 1, day 2)
http://www.artofproblemsolving.com/Wiki/index.php/1991_IMO_Problems/Problem_4

4 4
1 2
2 3
3 1
1 4

One possible answer is:
YES
1 2 3 4

i got AC but my code is correct when is graph is connect, who can solve this when the graph is arbitary?
plz give me your code.
(sorry for bad english) :D

This problem is so easy ^^!

Who can tell me?
I have WA1.
Thanks a lot.

Edited by author 03.05.2009 09:55

Edited by author 03.05.2009 09:56

Edited by moderator 13.05.2009 01:51

Bad test #13 has been corrected, solutions that had troubles with this test have been rejudged. 23 authors have got AC.

find the way from one to all airports
and each airport can be passed one time

Edited by author 24.05.2008 19:16

Why cant we just output first M prime numbers???
WA1

#include<stdio.h>
#include<math.h>
void main()
{int n,h;
 bool f;
 scanf("%i%i",&n,&n);
 printf("YES\n1");
 for(int i=2,j=1;j<n;i++)
   {h=(int)sqrt((float)i);
    f=0;
    for(int k=2;k<=h;k++)
      if((i%k)==0)
        {f=1;break;}
    if(!f){printf(" %i",i);j++;}
   }
}

AC!!!!!

Edited by author 06.08.2008 18:53

Validator was updated and some new tests were added.
Many authors got WA and TL because their heuristics failed new tests. Try to find new tricky tests if your heuristics still has AC.

6 5
1 2
2 4
4 3
5 6
3 2

Is the answer
YES
4 1 2 5 3
right?

The graph is not connected.

Can someone post test 6?

Thanks

Please, explain me why answer is always YES?
It's right only for connected graphs!

For example:
6 6
1 2 2 3 3 1
4 5 5 6 6 4
Answer is NO.

Submit ID is 1027752.

For test
5 4
1 2
2 3
1 3
4 5

My answer is NO.

But you can number flights: 1 2 3 4  :)

My solution should be OK for connected graphs. But the test set lacks for disconnected cases.

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.

Sorry, my english is too poor to describe my algo.
But here is a little tips:
For any neighbor positive integers a & b:
  GCD(a,b)=1

I.E. GCD(1,2)=1 GCD(2,3)=1 GCD(3,4)=1 GCD(4,5)=1 GCD(5,6)=1 GCD(6,7)=1 GCD(7,8)=1 GCD(8,9)=1 GCD(9,10)=1 ......