Graph painting

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

vector<int> g[101010];
bool r[101010];
int happy[101010];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++) {
		int n,m;
		cin>>n>>m;
		for (int i=0;i<m;i++) {
			int a,b;
			cin>>a>>b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		
		for (int i=1;i<=n;i+=2) r[i]=true;
		set<int> yay;
		for (int i=1;i<=n;i++) {
			if (r[i]) {
				for (auto x : g[i]) {
					if (r[x]) happy[i]++;
					else happy[i]--;
				}
			} else {
				for (auto x : g[i]) {
					if (r[x]) happy[i]--;
					else happy[i]++;
				}
			}
			if (happy[i]>0) yay.insert(i);
		}
		
		while (!yay.empty()) {
			int a=*yay.begin();
			yay.erase(a);
			if (r[a]) r[a]=false;
			else r[a]=true;
			happy[a]=-happy[a];
			if (r[a]) {
				for (auto x : g[a]) {
					if (r[x]) {
						happy[x]++;
						if (happy[x]==1) yay.insert(x);
					} else {
						happy[x]--;
						if (happy[x]==0) yay.erase(x);
					}
				}
			} else {
				for (auto x : g[a]) {
					if (r[x]) {
						happy[x]--;
						if (happy[x]==0) yay.erase(x);
					} else {
						happy[x]++;
						if (happy[x]==1) yay.insert(x);
					}
				}
			}
		}
		
		for (int i=1;i<=n;i++) {
			if (r[i]) cout<<"R ";
			else cout<<"B ";
		}
		cout<<"\n";
		
		for (int i=1;i<=n;i++) {
			g[i].clear();
			happy[i]=0;
			r[i]=false;
		}
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED