← 返回题目列表

Codeforces · 555/E

E. 计算机网络案例

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

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。