Android 安德鲁是银河系知名的侦探。现在,他正在准备防御黑客对主要计算机网络可能进行的攻击。
该网络中有 n 个顶点,某些顶点对通过 m 个无向通道连接。计划通过该网络传输q个重要消息,其中第i个消息必须通过一个或多个通道(也许通过一些中间节点)从顶点si发送到顶点di。
为了防止攻击,开发了一种特殊的算法。不幸的是,它只能应用于包含定向通道的网络。因此,由于无法创建新的通道,因此决定让每个现有的无向通道仅在两个方向之一上传输数据。
你的任务是确定是否可以为每个通道选择方向,以便每条 q 消息都能成功传输。
输入
第一行包含三个整数 n、m 和 q (1 ≤ n, m, q ≤ 2·105) — 节点、通道和重要消息的数量。
接下来 m 行各包含两个整数 vi 和 ui (1 ≤ vi, ui ≤ n, vi ≠ ui),这意味着节点 vi 和 ui 之间是一个通道。一对节点之间可以存在多个通道。
接下来 q 行包含两个整数 si 和 di (1 ≤ si, di ≤ n, si ≠ di) — 相应消息的源节点和目标节点的编号。
不保证最初可以传输所有消息。
输出
如果存在解决方案,请单行打印“Yes”(不带引号)。否则,打印“No”(不带引号)。
示例
输入 #1
4 4 2 1 2 1 3 2 3 3 4 1 3 4 2
输出 #1
Yes
输入 #2
3 2 2 1 2 3 2 1 3 2 1
输出 #2
No
输入 #3
3 3 2 1 2 1 2 3 2 1 3 2 1
输出 #3
Yes
注意
在第一个示例测试中,您可以指定方向,例如,如下所示:1 → 2、1 → 3、3 → 2、4 → 3。那么第一条消息的路径将为 1 → 3,第二条消息的路径为 4 → 3 → 2。
在第三个示例测试中,您可以指定方向,例如,如下所示:1 → 2、2 → 1、2 → 3。那么第一条消息的路径将为 1 → 2 → 3,第二条消息的路径为 2 → 1。