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.

Oh, what a trick! I was very much confused seeing > 400 people who solved this problem. I'm really annoyed beacuse in this case the problem is O(n + m) using a simple idea gcd(n,n + 1) = 1. But if the graph can be disconnected everything is much worse!!!

Graph can be disonnected.
Sample is.
But testset is weak... Why am I not surprised :)
My always "YES" program
got AC.

With such tests the problem is much easier than it is.
Please, change tests or statements!

Graph is always connected now.
Statements and tests are updated. So, the solution always exists.