CF576E.Painting Edges

Note the unusual memory limit for this problem.

You are given an undirected graph consisting of n vertices and m edges. The vertices are numbered with integers from 1 to n, the edges are numbered with integers from 1 to m. Each edge can be unpainted or be painted in one of the k colors, which are numbered with integers from 1 to k. Initially, none of the edges is painted in any of the colors.

You get queries of the form "Repaint edge e__i to color c__i". At any time the graph formed by the edges of the same color must be bipartite. If after the repaint this condition is violated, then the query is considered to be invalid and edge e__i keeps its color. Otherwise, edge e__i is repainted in color c__i, and the query is considered to valid.

Recall that the graph is called bipartite if the set of its vertices can be divided into two parts so that no edge connected vertices of the same parts.

For example, suppose you are given a triangle graph, that is a graph with three vertices and edges (1, 2), (2, 3) and (3, 1). Suppose that the first two edges are painted color 1, and the third one is painted color 2. Then the query of "repaint the third edge in color 1" will be incorrect because after its execution the graph formed by the edges of color 1 will not be bipartite. On the other hand, it is possible to repaint the second edge in color 2.

You receive q queries. For each query, you should either apply it, and report that the query is valid, or report that the query is invalid.

注意本题的内存限制较为特殊。

你将得到一个由 $n$ 个顶点和 $m$ 条边构成的无向图。顶点编号为 $1$ 到 $n$ 的整数，边编号为 $1$ 到 $m$ 的整数。每条边可以处于未染色状态，或被染成 $k$ 种颜色之一（颜色编号为 $1$ 到 $k$ 的整数）。初始时，所有边均未染色。

你将收到形如“将边 $e_i$ 染成颜色 $c_i$”的查询。在任意时刻，由同一种颜色的所有边所构成的子图必须是二分图。若执行该染色操作后此条件被破坏，则该查询视为无效，边 $e_i$ 保持其原有颜色；否则，边 $e_i$ 被成功染为颜色 $c_i$，该查询视为有效。

回忆：若一个图的顶点集可划分为两个部分，使得任意一条边的两个端点均不属于同一部分，则称该图为二分图。

例如，考虑一个三角形图（即包含三个顶点及三条边 $(1, 2)$、$(2, 3)$ 和 $(3, 1)$ 的图）。假设前两条边被染为颜色 $1$，第三条边被染为颜色 $2$。此时，查询“将第三条边染为颜色 $1$”是无效的，因为执行后颜色 $1$ 对应的子图将不再是二分图。而另一方面，“将第二条边染为颜色 $2$”则是可行的。

你将收到 $q$ 个查询。对每个查询，你需要要么执行它并报告该查询有效，要么报告该查询无效。

The first line contains integers n, m, k, q (2 ≤ n ≤ 5·105, 1 ≤ m, q ≤ 5·105, 1 ≤ k ≤ 50) — the number of vertices, the number of edges, the number of colors and the number of queries.

Then follow m edges of the graph in the form a__i, b__i (1 ≤ a__i, b__i ≤ n).

Then follow q queries of the form e__i, c__i (1 ≤ e__i ≤ m, 1 ≤ c__i ≤ k).

It is guaranteed that the graph doesn't contain multiple edges and loops.

第一行包含整数 $n$、$m$、$k$、$q$（$2 \leq n \leq 5\cdot10^5$，$1 \leq m,\,q \leq 5\cdot10^5$，$1 \leq k \leq 50$）——分别表示顶点数、边数、颜色数和查询数。

接下来 $m$ 行，每行描述图中的一条边，格式为 $a_i$, $b_i$（$1 \leq a_i,\,b_i \leq n$）。

接下来 $q$ 行，每行描述一个查询，格式为 $e_i$, $c_i$（$1 \leq e_i \leq m$，$1 \leq c_i \leq k$）。

保证图中不含重边和自环。

For each query print "YES" (without the quotes), if it is valid, or "NO" (without the quotes), if this query destroys the bipartivity of the graph formed by the edges of some color.

对于每个查询，如果该查询有效，则输出 “YES”（不带引号）；如果该查询会破坏由某种颜色的边构成的图的二分性，则输出 “NO”（不带引号）。