Every person can be next to at most two people. Therefore, if any person appears three or more times in the conditions, then the answer is No. This can be easily checked in a total of \(O(N+M)\).

Also, if there is a condition which forms a loop, like \((A_i,B_i)=(1,2),(1,3),(2,3)\), then the answer is also No. This can be checked in a total of \(O(N+M)\) time with Union-Find, BFS, or DFS.

Conversely, if the two conditions above are not violated, then the answer is determined to be Yes (without actually lining up!), so the problem has been solved.

Sample code (C++)