グラフ理論の言葉に置き換えて考えます。\(N\) 頂点 \(M\) 辺のグラフがあって、\(i\) 番目の辺は頂点 \(A_i\) と頂点 \(B_i\) を結んでいるとします。
このとき、問題文の条件を満たすような数列 \(X\) が存在することは、次の条件と同値です。

以下の条件を満たすように各頂点に \(0\) か \(1\) を書きこむことができる。

• 辺で結ばれた頂点同士には異なる数字が書きこまれている。

このような条件によって定義されるグラフのことを 二部グラフ と呼びます。よって、この問題はグラフが二部グラフかを判定するアルゴリズムを実装すれば正解できます。

グラフが二部グラフであるかどうかの判定は深さ優先探索(DFS) などのグラフ探索アルゴリズムを利用して実装できます。具体的には、以下の手順で頂点に数字を書きこんでいけばよいです。

• 各頂点についての情報を配列 \(X\) に格納する。
  • \(X[v] = -1\) である場合は頂点は未訪問であることを、
  • \(X[v] = 0\) である場合は頂点に \(0\) が書きこまれていることを、
  • \(X[v] = 1\) である場合は頂点に \(1\) が書きこまれていることを意味する。
• また、答えを管理するフラグ bipartite を用意して、はじめ true で初期化する。
• \(v=1, 2, \dots, N\) について次の操作を行う。
  • \(X[v] \neq -1\) である場合は頂点 \(v\) は訪問済みなので何もしない。
  • \(X[v] = -1\) である場合は以下の操作を行う。
    • 頂点 \(v\) に書きこむ数字を \(0\) と決め打つ。(つまり \(X[v] = 0\) とする)
    • その後、深さ優先探索を利用して、 \(v\) を含む連結成分に含まれる頂点に、隣り合う頂点が異なる数字となるように数字を書きこんでいく。
    • 書きこんでいく途中で、辺で結ばれた頂点同士に同じ数字が書きこまれた状態になった場合は、グラフは二部グラフではないので bipartite = false とする。
• 全ての頂点を訪問し終えた段階での bipartite の真偽が答えとなる。

計算量は \(\mathrm{O}(N + M)\) で十分高速です。C++ による実装例は次の通りです。

• 実装例

#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;
}