(Analysis by Benjamin Qi)

If both cows $b$ and $c$ admire cow $a$ then both $b$ and $c$ must have the same color. From now on, we can treat both $b$ and $c$ as the same cow; change all occurrences of $c$ to $b$ and merge the adjacency list of $c$ into that of $b$. Repeat this process while at least two distinct cows admire the same cow.

Once we reach a configuration in which a cow is admired by at most one cow this process terminates; we can just assign every cow a distinct color. If we always merge the smaller adjacency list of the two cows into the larger one then our solution runs in $O((N+M)\log N)$ time. We ensured that a few slow solutions did not pass but it is likely that many (not necessarily provable) heuristics passed anyways.

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

void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}

const int MX = 2e5+5;

int N,M;

int par[MX],cnt[MX];
queue<int> q;

void merge(int a, int b) {
a = par[a], b = par[b];
if (rpar[a].size() < rpar[b].size()) swap(a,b);
for (int t: rpar[b]) { par[t] = a; rpar[a].push_back(t); }
}

int main() {
setIO("fcolor");
cin >> N >> M;
for (int i = 0; i < M; ++i) {
int a,b; cin >> a >> b;
}
for (int i = 1; i <= N; ++i) {
par[i] = i; rpar[i].push_back(i);
}
while (q.size()) {
int x = q.front(); if (adj[x].size() <= 1) { q.pop(); continue; }