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 ......

See this:
6 6
1 2
2 3
3 1
4 5
5 6
6 4

The answer is NO

I think we can get the answer in O(n+m)...
Just use the method you mentioned...
Each node has two arcs which numbered x and x+1...

But there are no data like this...
I got AC although my program always prints "YES"...

is there an algo wich works in O(n+m) for disconnected graphs too?

I think no.
For exmaple, sometimes answer is NO and strategy 1,2,3,4... doesn't work.
When statements were incorrect (it was not said that graph is connected)
I and some my friends tried to solve it... but we couldn't find
even polynomial solution. So I think no.

If graph is connected ( current statement ), problem can be solved by dividing graph into chains ( like in #1441 ), chains are: k,k+1,...,l . This solution is absolutely correct.

No, I think the answer is
3 4 1 2 6 5

Sorry,I think your answer is wrong.
See the node 5:the number of one egde is 2,another is 6,gcd(2,6)=2<>1