Graph painting

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
  cin.sync_with_stdio(0);
  cin.tie(0);
  
  int tests; cin >> tests;
  
  while(tests--){
      vector<int> v[101010];
      int n, m; cin >> n >> m;
      bool ans[101010] = {0};
      for(int i = 0; i < m; i++){
	int a, b; cin >> a >> b;
	v[a].push_back(b);
	v[b].push_back(a);
      }
      vector<pair<int, int>> vs;
      for(int i = 1; i <= n; i++)
	vs.push_back({v[i].size(), i});
      sort(vs.begin(), vs.end());
      int cc = 0;
      for(int i = n-1; i >= 0; i--){
	int cur = vs[i].second;
	
	int ad = 0;
	for(auto f: v[cur]){
	  if(ans[f] == 0){
	    ad++;
	  }
	  else
	    ad--;
	}
	if(ad > 0){
	  cc+=ad;
	  ans[cur] = 1;
	}
	
	if(cc >= m/2)
	  break;
      }
      for(int i = 1; i <= n; i++){
	if(ans[i] == 1)
	  cout << 'R' << " ";
	else
	  cout << 'B' << " ";
      }
      cout << endl;
	
  } 
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED