根据不知从何而来的传统，考前需要写数据结构。
Part 1 如何判断二分图
你要是用染色法暴力过了这道题那就只能说是真神仙……
但是我们可以使用染色的思想。
考虑到颜色数不多，可以开 \(k\) 个拓展域并查集，对于原图每个点我们拆成两个：\(i\) 和 \(i+n\)，如果 \(i+n\) 和 \(j\) 连边了（\(i,j\le n\)），说明 \(i\) 和 \(j\) 必定不在同一个部分中。于是对于原图每条边 \((u,v)\)，并查集中 \((u+n,v),(u,v+n)\) 连边即可。
一个图为二分图，当且仅当 \(\forall u,v\le n,u\neq v,s.t.\ getf(u)\neq getf(v)\)。
Part 2 考虑所有操作都强制被执行
那么只需要判断执行后是否为二分图。
不难发现，在一种颜色中，某条边的出现在时间轴上为若干个区间，所有颜色所有边的出现区间总数是 \(O(q)\) 的。
考虑如何求出一条边的出现区间。直接从后往前扫时间轴，设当前时间为 \(i\)，记录 \(cur_k\) 表示 \(i+1\) 到 \(q\) 时刻 \(e_k=(u,v)\) 最后的出现位置。当我们在 \(i\) 时刻改变了 \(e_k\) 的颜色 \(col_k\to col'_k\)，那么 \(e_k\) 在 \(col'_k\) 颜色中的出现区间即为 \([i,cur_k-1]\)。
或者可以这样说，假设一条边在 \(i\) 时刻和 \(j\) 时刻分别变换了颜色，那么在 \(i\) 时刻变换的颜色的出现区间为 \([i,j-1]\)。
求出了对于每条边在每种颜色的出现区间，就可以线段树分治了。
按照时间轴建立线段树。
类似标记永久化的思想，把连接操作挂在线段树上不超过 \(O(\log q)\) 个节点上，然后遍历整棵树，在当前节点上将这个节点的操作全部作用到上文的拓展域并查集即可。
遍历完一棵子树，我们需要撤销这棵子树内所有操作的贡献，所以需要使用可撤销并查集。
Part 3 回到题目要求
还是考虑某条边的出现区间。
假设一条边在 \(i\) 时刻和 \(j\) 时刻分别变换了颜色，那么在 \(i\) 时刻这条边会多出来一个出现区间为 \([i,j-1]\)。
至于这个区间是在哪个颜色的，分情况讨论：
- 如果 \(i\) 操作被执行了，那么就是 \(i\) 操作的颜色
- 否则就是 \(i\) 操作之前，这条边本来的颜色。
我们可以先假装所有操作都被执行了。
由于线段树遍历是按照时间顺序的，那么我们可以维护每条边此时此刻的颜色，然后判断此时此刻的操作是否执行，如果执行，就将颜色改为这次操作指定的颜色。否则就将这次操作的颜色改为这条边本来的颜色，然后后面再遇到这个操作时就可以正常染色了。
时间复杂度是经典的 \(2\) 只 \(\log\)。
代码很好写，那就不放了。