We consider the problem using graph theory terms. Consider a graph with \(N\) vertices and \(M\) edges, where the \(i\)-th edge connects vertex \(A_i\) and vertex \(B_i\).
Then, there exists a sequence \(X\) satisfying the condition in the problem statement if and only if:

one can write \(0\) or \(1\) on each vertex so that:

• each pair of vertices connected by an edge has different numbers written on them.

Such a graph is called a bipartite graph. Thus, one can solve this problem by implementing an algorithm that determines if a graph is bipartite.

One can determine if a graph is bipartite by a graph-searching algorithm like Depth-First Search (DFS). Specifically, write numbers onto the vertices by the following procedure.

• We maintain an array \(X\) to store the state of vertices.
  • \(X[v] = -1\) means the vertex is unvisited;
  • \(X[v] = 0\) means \(0\) is written on the vertex;
  • \(X[v] = 1\) means \(1\) is written on the vertex.
• We also use a flag bipartite to store the answer, initialized with true.
• For each \(v=1, 2, \dots, N\), do the following operation:
  • If \(X[v] \neq -1\), then we have already visited vertex \(v\), so do nothing.
  • If \(X[v] = -1\), do the following:
    • Assume that we write \(0\) on vertex \(v\). (In other words, let \(X[v] = 0\).)
    • Then, perform DFS to write numbers on the vertices in the same connected component, so that adjacent vertices have different numbers written on them.
    • If it turns out that adjacent vertices have the same numbers written on them during the DFS, then the graph is not bipartite, so let bipartite = false.
• After visiting all the vertices, bipartite stores the answer.

The complexity is \(\mathrm{O}(N + M)\), which is fast enough. Sample code in C++ follows.

• Sample code

#include <iostream>
#include <vector>
using namespace std;

constexpr int nmax = 200200;
int N, M;
int A[nmax], B[nmax];
vector<int> g[nmax];
int X[nmax];
int bipartite = true;

void dfs(int c, int x) {
  X[c] = x;
  for (auto& d : g[c]) {
    if (X[d] == -1) {
      dfs(d, 1 - x);
    } else if (X[d] == X[c]) {
      bipartite = false;
    }
  }
}

int main() {
  cin >> N >> M;
  for (int i = 0; i < M; i++) cin >> A[i], A[i]--;
  for (int i = 0; i < M; i++) cin >> B[i], B[i]--;
  for (int i = 0; i < M; i++) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }

  for (int i = 0; i < N; i++) X[i] = -1;
  for (int i = 0; i < N; i++) {
    if (X[i] == -1) dfs(i, 0);
  }
  cout << (bipartite ? "Yes" : "No") << endl;
}