Case of Computer Network

Description

Andrewid 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 \le n,m,q \le 2 \times 10^5$) — the number of nodes, channels and important messages.

Next $m$ lines contain two integers each, $v_i$ and $u_i$ ($1 \le v_i,u_i \le n, \ v_i \neq 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 \le s_i, \le d_i \le n, \ s_i \neq 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.

Solution

给出一个$n$个点，$m$条边的无向图，问是否存在一种给每条边定向把它转成有向图的方法，使$q$个点对$s_i,d_i$，$s_i$可以到达$d_i$。可以输出”Yes”（不带引号），不可以输出”No”（不带引号）。

对于一个点对$s_i,d_i$，$s_i$到$d_i$所有路径的边集一定是一些由割边连接着的边双，割边必须要强制定向。至于边双，发现每个边双一定可以给它定向使它强连通，该强连通子图任意两个点都可以互相到达，所以只需要处理割边上的冲突。把原图的每个边双缩点，使原图成为一个森林（原图可能不联通）。再对进行树上差分，算出每条边的两种方向的个数。若某个点对$s_i,d_i$不在同一个联通块内，则不存在方案。否则算出两个点的LCA$l_i$，对$u_i$到$l_i$打上向上边的标记，对$l_i$到$v_i$打上向下边的标记。最后DFS一遍算出每条边的两种方向的个数，枚举每条边，若某条边两种方向存在冲突，则不存在方案，否则存在方案。

Standrad

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 200010, M = 200010, P = 18;

int n, m, q;
struct Graph {
    int tot, head[N];
    Graph() {
        tot = -1;
        memset(head, -1, sizeof(head));
        return;
    }
    struct Edge {
        int p, next;
    } edge[M << 1];
    inline void Add(int u, int v) {
        edge[++tot] = (Edge) {v, head[u]};
        head[u] = tot;
        return;
    }
} og, ng;

int f[N], link[N];
int Gf(int k) {
    return (f[k] != k) ? (f[k] = Gf(f[k])) : (k);
}
int Link_Gf(int k) {
    return (link[k] != k) ? (link[k] = Link_Gf(link[k])) : (k);
}

int k = 0, dfn[N], low[N], fa[N][P], dep[N];
int tk = 0, t[N];

void Tarjan(int u, int comedge) {
    dfn[u] = low[u] = ++k;
    t[++tk] = u;
    for (int i = og.head[u]; ~i; i = og.edge[i].next) {
        int v = og.edge[i].p;
        if (!dfn[v]) {
            Tarjan(v, i);
            low[u] = min(low[u], low[v]);
        } else if ((i ^ 1) != comedge) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        if (~comedge) fa[u][0] = og.edge[comedge ^ 1].p;
        for (int i; i = t[tk--], i != u; f[i] = u);
    }
    return;
}

void DFS(int u) {
    dep[u] = dep[fa[u][0]] + 1;
    for (int i = ng.head[u]; ~i; i = ng.edge[i].next)
        DFS(ng.edge[i].p);
    return;
}

void Pre() {
    for (int j = 1; j < P; ++j)
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    return;
}

int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 0, j = dep[u] - dep[v]; j; ++i, j >>= 1)
        if (j & 1) u = fa[u][i];
    if (u == v) return u;
    for (int i = P - 1; ~i; --i)
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    return fa[u][0];
}

int sum1[N], sum2[N];

void Count(int u) {
    for (int i = ng.head[u]; ~i; i = ng.edge[i].next) {
        int v = ng.edge[i].p;
        Count(v);
        sum1[u] += sum1[v];
        sum2[u] += sum2[v];
    }
    return;
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
        link[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        og.Add(u, v);
        og.Add(v, u);
        link[Link_Gf(v)] = Link_Gf(u);
    }
    for (int i = 1; i <= n; ++i)
        if (link[i] == i) Tarjan(i, -1);
    for (int i = 1; i <= n; ++i)
        if (fa[i][0]) ng.Add(fa[i][0] = Gf(fa[i][0]), i);
    for (int i = 1; i <= n; ++i)
        if (link[i] == i) DFS(i);
    Pre();
    for (int i = 1; i <= q; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (Link_Gf(u) != Link_Gf(v)) {
            puts("No");
            return 0;
        }
        u = Gf(u);
        v = Gf(v);
        int l = LCA(u, v);
        ++sum1[u];
        --sum1[l];
        ++sum2[v];
        --sum2[l];
    }
    for (int i = 1; i <= n; ++i)
        if (link[i] == i) Count(i);
    bool flag = 1;
    for (int i = 1; i <= n; ++i)
        if (sum1[i] && sum2[i]) {
            flag = 0;
            break;
        }
    if (flag) puts("Yes");
    else puts("No");
    return 0;
}