请注意此问题的异常内存限制。
给定一个由 n 个顶点和 m 个边组成的无向图。顶点用 1 到 n 的整数编号,边用 1 到 m 的整数编号。每条边可以不涂漆,也可以涂上 k 种颜色之一,这些颜色用 1 到 k 的整数编号。最初,没有任何边缘被涂上任何颜色。
您会收到“将边缘 ei 重新绘制为颜色 ci”形式的查询。在任何时候,由相同颜色的边形成的图必须是二部的。如果在重绘之后违反了此条件,则查询被认为是无效的并且边 ei 保持其颜色。否则,边 ei 被重新绘制为颜色 ci,并且查询被认为是有效的。
回想一下,如果图的顶点集可以分为两部分,并且没有边连接相同部分的顶点,则该图称为二分图。
例如,假设给定一个三角形图,即具有三个顶点和边 (1, 2)、(2, 3) 和 (3, 1) 的图。假设前两条边被绘制为颜色 1,第三条边被绘制为颜色 2。那么“用颜色 1 重新绘制第三条边”的查询将是不正确的,因为执行后由颜色 1 的边形成的图将不是二分图。另一方面,可以用颜色 2 重新绘制第二条边。
您收到 q 个询问。对于每个查询,您应该应用它并报告查询有效,或者报告查询无效。
输入
第一行包含整数 n、m、k、q (2 ≤ n ≤ 5·105, 1 ≤ m, q ≤ 5·105, 1 ≤ k ≤ 50) — 顶点数、边数、颜色数和查询数。
然后按照 ai, bi (1 ≤ ai, bi ≤ n) 的形式跟踪图的 m 条边。
然后遵循 ei, ci (1 ≤ ei ≤ m, 1 ≤ ci ≤ k) 形式的 q 个查询。
保证图不包含多个边和环。
输出
对于每个查询,如果有效,则打印“YES”(不带引号);如果该查询破坏了由某种颜色的边缘形成的图形的二分性,则打印“NO”(不带引号)。
示例
输入 #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