给定一个 \(n\) 个节点和 \(m\) 条边组成的无向图。节点编号为 $1\sim n$ ，边的编号为 $1\sim m$ 。每条边可以没有颜色，也可以涂成 $1\sim k$ 中的某种颜色。最初任何边都没有颜色。

你将得到一些形如“将边 \(e_i\) 涂成颜色 \(c_i\) ”的请求，你必须保证任何时候被涂成同种颜色边构成的图示一个二分图。如果一个请求会违反这个条件则这个请求无效，边 \(e_i\) 保留原来的颜色(或者保持无色)；否则就执行这个请求所描述的涂色操作。总共有 \(q\) 个请求，你的任务是汇报每条请求是否被执行。

第一行四个整数 \(n,m,k,q\) ，分别是节点数、边数、颜色数、请求数。

接下来 \(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)\) ，表示一条请求。

每条请求输出一行，如果被执行输出 YES ，否则输出 NO 。

$2\leq n\leq 5\times 10^5$
$1\leq m,q\leq 5\times 10^5$
$1\leq k\leq 50$