\(N\) 頂点 のグラフであって、 \(A_i\) と \(B_i\) を辺で結んだグラフを考えます。 問題文の条件をみたすような順列が存在する事は、辺で結ばれたどの \(2\) 点の和も \(3\) の倍数となるように各頂点に \(0,1,2\) のいずれかを割り当てる方法であって、 \(1\) が \([\frac{N+2}{3}]\) 個 , \(2\) が \([\frac{N+1}{3}]\) 個 , \(0\) が \([\frac{N}{3}]\) 個であるような割り当て方が存在する事と同値です。 ただし, \([x]\) で\(x\) 以下の最大の整数を表します。この場合、頂点 \(i\) に割り当てられた数は \(P_i\) を \(3\) で割った余りに対応します。

まず、連結成分ごとに考えます。 \(1\) を割り当てられた頂点と辺で結ばれた頂点はすべて \(2\) を割り当てられたなければならず、 \(2\) を割り当てられた頂点と辺で結ばれた頂点はすべて \(1\) を割り当てられたなければなりません。すなわち \(1\) または \(2\) を割り当てられた頂点を含む連結成分は \(0\) が割り当てられた頂点を含まず、さらに二部グラフでなければなりません。一方で、 \(0\)が割り当てられた頂点を含む連結成分に含まれる頂点にはすべて \(0\) が割り当てられていなくてはなりません。

以上をまとめると、各連結成分について、それが二部グラフをなしているならば、その間に辺が存在しないような点集合のサイズをそれぞれ \(a,b\) として,

• \(1\)が割り当てられた頂点が \(a\) 個, \(2\) が割り当てられた頂点が \(b\) 個
• \(1\)が割り当てられた頂点が \(b\) 個, \(2\) が割り当てられた頂点が \(a\) 個
• \(0\)が割り当てられた頂点が \(a+b\) 個

のいずれかしか割り当て方が無く、二部グラフでないならばすべての頂点に \(0\) を割り当てるしかない事が分かります。

以上から、各二部グラフに上記の\(3\)パターンのいずれを振り分けて, 条件をみたすようにできるかを確かめればよいです。これは動的計画法によって解くことができます。 具体的には、二部グラフであるような連結成分が見つかるたびに \(dp[i][j]=\) ( それまでに見つかった各二部グラフの連結成分に \(3\)パターンのいずれかを振り分ける方法であって, \(1\) が \(i\) 個 , \(2\) が \(j\) 個の頂点に割り当てられるような割り当て方があるか ) を順に更新していけばよいです。

各連結成分についてそれが二部グラフであるかの判定およびサイズは合計で \(O(N+M)\)で求められ、動的計画法についてはナイーブに行うと \(O(N^3)\) であり厳しいように見えますが, 管理する配列のサイズは約 \(\frac{N}{3}\times \frac{N}{3}\) であるので定数倍が速く、操作も軽い事から十分間に合います。よってこの問題を解くことが出来ました

C++による実装例:

#include <bits/stdc++.h>
using namespace std;

#define N 1010
#define MOD 998244353
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep3(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int cnt[2];
bool binary;
int col[N];
vector<int>e[N];
bool dp[(N / 3)][(N / 3)];

void dfs(int k, int cc) {
	if (col[k] != -1) {
		if (col[k] != cc)binary = false;
		return;
	}
	col[k] = cc;
	cnt[cc]++;
	int sz = e[k].size();
	rep(i, sz) {
		dfs(e[k][i], (cc ^ 1));
	}
	return;
}




int main(void) {
	int n, m, k;
	int x, y, z;
	rep(i, N / 3)rep(j, N / 3)dp[i][j] = false;
	rep(i, N)col[i] = -1;
	dp[0][0] = true;
	cin >> n >> m;
	k = (n + 2) / 3;
	rep(i, m) {
		cin >> x >> y;
		e[x - 1].pb(y - 1);
		e[y - 1].pb(x - 1);
	}
	y = 0;
	rep(ii, n) {
		if (col[ii] == -1) {
			rep(j, 2)cnt[j] = 0;
			binary = true;
			dfs(ii, 0);
			if (binary) {
				x = min(cnt[0], cnt[1]);
				y += max(cnt[0], cnt[1]);
				z = min(k, y);
				rep3(i, z, x) {
					rep3(j, z, x) {
						if ((cnt[0] <= i) && (cnt[1] <= j))dp[i][j] = (dp[i][j] | dp[i - cnt[0]][j - cnt[1]]);
						if ((cnt[1] <= i) && (cnt[0] <= j))dp[i][j] = (dp[i][j] | dp[i - cnt[1]][j - cnt[0]]);
					}
				}
			}
		}
	}
	x = (n + 2) / 3;
	y = (n + 1) / 3;
	if (dp[x][y])cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}