Let a type of vertex v be the set of vertices that it is connected to, including the vertex v. Each type has its own label.

For example, if we have the edges:

1 2

1 3

The set of vertices of 1 is {1, 2, 3};

For optimal comparing we hash the sets.

From condition |xu-xv| ≤ 1, it's clear that each vertex can only be connected with 3 other types of vertices, one with the same type and label, and two with different types: one with a label+1 and one with a label-1.

When xu-xv = 0, u and v need to be connected to the same set of vertices (be the same type), otherwise the answer is NO.

When |xu-xv| = 1, u and v need to be connected to different sets of vertices (be different types)

For each vertex, we keep two types that it is connected to, D[x] — type of vertex with decreased label and I[x] type with increased one.

Construction and checking:

We start in an arbitrary vertex v, put it a label 5000000 (to have a reserve in decreasing) and check if it isn't connected to more than mentioned 3 types. Put the different types in D[x] and I[x], doesn't matter we way of attributing.

Start a BFS or DFS from v and do the same algorithm.

My O(NlogN+M) solution for D problem using hashing. http://codeforces.me/contest/794/submission/27087484

Another greedy solution for D code.