Painting Edges

题意翻译

给定一张 $n$ 个点 $m$ 条边的无向图。 一共有 $k$ 种颜色，一开始，每条边都没有颜色。 定义**合法状态**为仅保留**染成 $k$ 种颜色中的任何一种颜色**的边，图都是一张二分图。 有 $q$ 次操作，第 $i$ 次操作将第 $e_i$ 条边的颜色染成 $c_i$。 但并不是每次操作都会被**执行**，只有当执行后仍然合法，才会执行本次操作。 你需要判断每次操作是否会被执行。 $n,m,q \le 5 \times 10^5$，$k \le 50$。

题目描述

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.

输入输出格式

输入格式

The first line contains integers $ n $ , $ m $ , $ k $ , $ q $ ( $ 2<=n<=5·10^{5} $ , $ 1<=m,q<=5·10^{5} $ , $ 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.

输出格式

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.

输入输出样例

输入样例 #1

3 3 2 5
1 2
2 3
1 3
1 1
2 1
3 2
3 1
2 2

输出样例 #1

YES
YES
YES
NO
YES