← 返回题目列表

Codeforces · 576/E

E. 绘画边缘

中文机器翻译题面 查看原题

请注意此问题的异常内存限制。

给定一个由 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