CF576E Painting Edges

注意本题的特殊内存限制。 给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。顶点编号为 $1$ 到 $n$，边编号为 $1$ 到 $m$。每条边可以未染色，或被染成 $k$ 种颜色之一（颜色编号为 $1$ 到 $k$）。最初，所有边都未染色。 你会收到形如“将边 $e_i$ 重新染成颜色 $c_i$”的询问。任何时刻，对于同一种颜色所形成的子图，都必须是二分图。如果某次重染操作使该颜色的子图不是二分图，则该操作无效，边 $e_i$ 保持原有颜色。否则，执行染色，查询有效。 回忆：如果一个图的顶点可以划分成两个部分，使得任何一条边的两端分别位于这两个部分，该图称为二分图。 例如，假设你有一个三角形图，即顶点 $1,2,3$，边为 $(1,2)$、$(2,3)$、$(3,1)$。假设前两条边被染成颜色 $1$，第三条边被染成颜色 $2$，此时若想将第三条边重染为颜色 $1$，由于颜色 $1$ 子图将变成一个三角形，这不是一个二分图，所以这个操作无效。另一方面，你可以将第二条边重染为颜色 $2$。 你会收到 $q$ 个查询。对于每个查询，你应当判断此次操作是否合法，如果合法输出“YES”，否则输出“NO”。

第一行包含四个整数 $n$、$m$、$k$、$q$（$2 \leq n \leq 5\cdot 10^5$，$1 \leq m, q \leq 5\cdot 10^5$，$1 \leq k \leq 50$），表示顶点数、边数、颜色数和查询数。 接下来 $m$ 行，每行两个整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$），表示一条边连接 $a_i$ 和 $b_i$。 接下来 $q$ 行，每行两个整数 $e_i$、$c_i$（$1 \leq e_i \leq m$，$1 \leq c_i \leq k$），表示一次操作：将第 $e_i$ 条边重染为颜色 $c_i$。 保证图中没有重边或自环。

对于每个查询，如果操作合法输出“YES”，否则输出“NO”。

由 ChatGPT 5 翻译