当前没有测试数据。

人际关系（无数据）

题目背景

本题作者还没有造数据！

QwQ 正在回忆他成为奆佬之前的经历。升入高中时，班级里有一些以前认识的初中同学，还有一些不认识的同学。但是经过慢慢的了解，有些同学一点一点的认识了。

题目描述

QwQ 所在的高中班级有 $n$ 个人。

由于记性不好，人 $u$ 可能认识 $v$，但是 $v$ 不一定认识 $u$。

学期开始时，有 $m$ 个认识关系，$u_i$ 和 $v_i$，表示 $u_i$ 认识 $v_i$。（$1 \le i \le m$）

同学们之间会互相介绍，如果三个人 $u$、$v$、$w$ 中，$u$ 与 $v$ 互相认识，$v$ 与 $w$ 互相认识，$u$ 与 $w$ 不互相认识，那么在满足这个条件的第一个瞬间，$u$ 与 $w$ 互相认识了。

在接下的时光里，发生了 $q$ 个事件，每个事件发生在 $t_j$（记开学为 $0$，$0 < t_i \le 10^9$），事件发生的一瞬间导致了 $u_j$ 认识了 $v_j$。（$1 \le j \le q$）

QwQ 回忆了 $k$ 个时刻，第 $x$ 个记为 $a_x$，同时给定 $u_x$ 和 $v_x$，你需要回答 $a_x + 0.5$ 时有多少个集合，里面的人两两互相认识，并且回答此时 $u_x$ 是否认识 $v_x$。（$1 \le x \le k$）

输入格式

第一行四个正整数 $n$、$m$、$q$、$k$。

接下来 $m$ 行，每行两个正整数 $u_i$、$v_i$，表示开学时（时刻 $0$ 时）$u_i$ 认识 $v_i$。

接下来 $q$ 行，每行三个正整数 $t_i$、$u_i$、$v_i$，表示时刻 $t_i$ 时，$u_i$ 认识 $v_i$。

接下来 $k$ 行，每行一个非负整数 $a_i$，两个正整数 $u_i$、$v_i$，表示回忆时刻 $a_i + 0.5$ 时，有几个尽可能大的集合使在其中的同学两两认识，$u_i$ 认不认识 $v_i$。

输出格式

输出 $k$ 行，每行一个非负整数 $c_i$，一个字符串 $s_i$，$c_i$ 表示该回答时有几个尽可能大的集合使在其中的同学两两认识，注意一个同学自己不算作，$s_i \in \{\text{Yes},\text{No}\}$，表示 $u_i$ 是否认识 $v_i$。

样例 #1

样例输入 #1

s1

样例输出 #1

o1

样例 #2

样例输入 #2

s2

样例输出 #2

o2

样例 #3

样例输入 #3

s3

样例输出 #3

o3

提示

样例解释

样例1

略

样例2

略

---

数据范围

对于 $15\%$ 的数据，$n,m,q,k \le 12$。

对于 $40\%$ 的数据，$n,m,q,k \le 2000$。

对于另外 $20\%$ 的数据，满足 $t_i, a_i \le 1000$。

对于 $100\%$ 的数据，$1 \le n,m,q,k \le 2 \times 10^5$，$1 \le u_i, v_i \le n$，$1 \le t_i \le 10^9$，$0 \le a_i \le 10^9$。保证输出 $0 \le c_i \le \lfloor \frac{n}{2} \rfloor$，$s_i \in \{\text{Yes},\text{No}\}$。保证所有数据在 64-bit 有符号整数范围内，保证输入数据单个在 8MiB 以内。

---

提示

一个同学自己构成的集合不算做两两认识的集合。