题目描述

一方通行出事了。

现在计划用 Misaka Network 的来弥补一方通行的计算力。Misaka Network 由 $N$ 个个体组成，个体之间由 $N-1$ 条边连接，边连接的两个个体可以通过脑电波互通信息。Misaka Network 的构造保证任意个体能够直接或间接通信，即构成一棵树。

现在要让一方通行接入这个网络，一方通行可以选择一部分个体，并与这些个体之间通信。但是出于稳定性要求，有一些限制条件，每个条件给出 $a, \mathrm{type}$：

• $\mathrm{type} = 0$：如果一方通行不和 $a$ 号个体直接通信，那么他不能和任何距离 $a$ 在 $[L,R]$ 之间的个体直接通信
• $\mathrm{type} = 1$：如果一方通行不和 $a$ 号个体直接通信，那么他必须和所有距离 $a$ 在 $[L,R]$ 之间的个体直接通信
• $\mathrm{type} = 2$：如果一方通行决定和 $a$ 号个体直接通信，那么他不能和任何距离 $a$ 在 $[L,R]$ 之间的个体直接通信
• $\mathrm{type} = 3$：如果一方通行决定和 $a$ 号个体直接通信，那么他必须和所有距离 $a$ 在 $[L,R]$ 之间的个体直接通信

其中 $L, R$ 都是 Misaka Network 的参数，各个限制都是一样的。

如果一种通信方案能满足所有条件，那么一方通行就能成功接入网络。一方通行想知道是否能够成功接入网络。

输入格式

第一行四个整数 $N, M, L, R$。

接下来 $N-1$ 行，每行两个整数 $u, v$，表示 $u$ 号个体和 $v$ 号个体之间有一条边。

接下来 $M$ 行，每行两个整数 $a, \mathrm{type}$，表示一组限制条件。

输出格式

一行一个字符串 YES 或者 NO。若为 NO，表示一方通行无论如何都无法接入网络，否则为 YES。

样例 1

input

3 2 1 2
1 2
1 3
2 1
3 1

output

YES

一种可行的方案是和所有个体都建立直接通信

样例 2

input

3 4 1 2
1 2
1 3
1 0
1 1
1 2
1 3

output

NO

见附加文件。

数据范围与提示

对于所有数据 $1 \leq N,M \leq 50000$，$1 \leq L \leq R \leq 50000$。