题目描述

给定一张 $n$ 个点 $m$ 条边的无向图。一共有 $k$ 种颜色，一开始，每条边都没有颜色。

定义合法状态为仅保留染成 $k$ 种颜色中的任何一种颜色的边，图都是一张二分图。

有 $q$ 次操作，第 $i$ 次操作将第 $e_i$ 条边的颜色染成 $c_i$。但并不是每次操作都会被执行，只有当执行后仍然合法，才会执行本次操作。

你需要判断每次操作是否会被执行。

输入格式

第一行四个整数 $n, m, k, q$，$n,m,q \le 5 \times 10^5$，$k \le 50$。

接下来 $m$ 行，每行两个整数 $a_i, b_i$，表示一条无向边。

接下来 $q$ 行，每行两个整数 $e_i, c_i$，表示一个询问。

输出格式

对于每个询问，在一行中输出 YES 或 NO 表示答案。

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

YES
YES
YES
NO
YES