Codeforces Round 310 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

graphs

trees

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Case of Computer Network

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAndrewid the Android is a galaxy-known detective. Now he is preparing a defense against a possible attack by hackers on a major computer network.

In this network are *n* vertices, some pairs of vertices are connected by *m* undirected channels. It is planned to transfer *q* important messages via this network, the *i*-th of which must be sent from vertex *s*_{i} to vertex *d*_{i} via one or more channels, perhaps through some intermediate vertices.

To protect against attacks a special algorithm was developed. Unfortunately it can be applied only to the network containing directed channels. Therefore, as new channels can't be created, it was decided for each of the existing undirected channels to enable them to transmit data only in one of the two directions.

Your task is to determine whether it is possible so to choose the direction for each channel so that each of the *q* messages could be successfully transmitted.

Input

The first line contains three integers *n*, *m* and *q* (1 ≤ *n*, *m*, *q* ≤ 2·10^{5}) — the number of nodes, channels and important messages.

Next *m* lines contain two integers each, *v*_{i} and *u*_{i} (1 ≤ *v*_{i}, *u*_{i} ≤ *n*, *v*_{i} ≠ *u*_{i}), that means that between nodes *v*_{i} and *u*_{i} is a channel. Between a pair of nodes can exist more than one channel.

Next *q* lines contain two integers *s*_{i} and *d*_{i} (1 ≤ *s*_{i}, *d*_{i} ≤ *n*, *s*_{i} ≠ *d*_{i}) — the numbers of the nodes of the source and destination of the corresponding message.

It is not guaranteed that in it initially possible to transmit all the messages.

Output

If a solution exists, print on a single line "Yes" (without the quotes). Otherwise, print "No" (without the quotes).

Examples

Input

4 4 2

1 2

1 3

2 3

3 4

1 3

4 2

Output

Yes

Input

3 2 2

1 2

3 2

1 3

2 1

Output

No

Input

3 3 2

1 2

1 2

3 2

1 3

2 1

Output

Yes

Note

In the first sample test you can assign directions, for example, as follows: 1 → 2, 1 → 3, 3 → 2, 4 → 3. Then the path for for the first message will be 1 → 3, and for the second one — 4 → 3 → 2.

In the third sample test you can assign directions, for example, as follows: 1 → 2, 2 → 1, 2 → 3. Then the path for the first message will be 1 → 2 → 3, and for the second one — 2 → 1.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/22/2024 13:25:45 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|