/*
  No.3508 OR Mapping
  https://yukicoder.me/problems/13182

  APPROACH:
  
  We need to make every vertex's value = 2^K - 1 (all K bits set).
  Each time we move to vertex j at time T (1-indexed), we OR in (T mod 2^K).
  
  Key observations:
  
  1. REACHABILITY: Every vertex must be reachable from vertex 1.
     If any vertex is unreachable, we can never write to it → No.
  
  2. VERTEX 1 MUST BE ON A CYCLE: Vertex 1's value only changes when we
     move TO it. If vertex 1 has no incoming edges from reachable nodes
     (i.e., not on any cycle), its value stays 0 → No (for K >= 1).
  
  3. STRONGLY CONNECTED COMPONENTS (SCCs):
     Within an SCC with cycle-gcd g (gcd of all cycle lengths),
     if we enter the SCC at time T0, vertices in the SCC can be visited
     at times T0, T0+g, T0+2g, T0+3g, ...
     The OR of (T0 + i*g) mod 2^K over all i >= 0 equals 2^K - 1
     iff g is ODD.
     
     - If g is odd: gcd(g, 2^K) = 1, so multiples of g cover all residues
       mod 2^K, and the OR of all visited time values = 2^K - 1. ✓
     - If g is even: e.g. g=2, then every other bit position is unreachable
       for certain vertices (those always visited at even times), so
       we can never OR in all bits. ✗
  
  4. TRIVIAL SCCs (single vertex, no self-loops allowed by constraints):
     Visited at one specific time T per visit. Multiple visits are possible
     by re-entering only if in the condensed DAG there are cycles, but the
     condensed DAG is acyclic. So effectively visited at one time T.
     
     However, we can adjust T arbitrarily by looping in any predecessor SCC
     (which has odd gcd, so we can add any multiple of an odd number to T,
     effectively reaching any residue mod 2^K).
     
     For a trivial SCC to accumulate all bits: we need to visit it at
     multiple different times... but it's a DAG node, visited at most once
     per "session". Actually we can re-enter it if there's a path back
     to it from itself — but that would make it non-trivial in Tarjan.
     
     Wait: a trivial SCC means there's no cycle through it. So we visit it
     at exactly one time T in any traversal. For it to get value 2^K - 1,
     we need T mod 2^K = 2^K - 1. We can arrange this by looping in a
     predecessor SCC with odd gcd to adjust T to any desired residue.
     Since SCC(1) has odd gcd (condition 2), this is always achievable.
  
  ALGORITHM:
  1. Find all SCCs (Tarjan/Kosaraju).
  2. Check all vertices reachable from vertex 1.
  3. Check SCC(1) is non-trivial with odd cycle-gcd.
  4. Check every non-trivial SCC reachable from vertex 1 has odd cycle-gcd.
  
  Computing cycle-gcd of an SCC:
  - BFS from any root within the SCC.
  - For each edge (u -> v) in the SCC, contribute (dist[u] + 1 - dist[v]).
    (Tree edges contribute 0; back/cross edges contribute cycle lengths.)
  - g = gcd of all non-zero contributions.
  
  Complexity: O(N + M) for SCC + O(N + M) for gcd computation = O(N + M).
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 500005
#define MAXM 500005

/* Forward graph */
int head[MAXN], nxt[MAXM], to_v[MAXM];
/* Reverse graph */
int rhead[MAXN], rnxt[MAXM], rto_v[MAXM];
int ecnt = 0;

int N, M;
long long K;

/* SCC */
int comp[MAXN];       /* SCC id of each vertex (1-indexed SCC ids) */
int scc_size[MAXN];   /* size of each SCC */
int scc_head[MAXN];   /* head of linked list of vertices in SCC */
int scc_nxt[MAXN];    /* linked list next pointer (0 = end) */
int scc_cnt = 0;

/* Kosaraju DFS order */
int order_arr[MAXN];
int ord_cnt = 0;
int vis[MAXN];

/* BFS */
int dist[MAXN];
int bfs_q[MAXN];

/* Iterative DFS stacks */
int stk[MAXN], stk_e[MAXN];

void add_edge(int u, int v) {
    ecnt++;
    to_v[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
    rto_v[ecnt] = u; rnxt[ecnt] = rhead[v]; rhead[v] = ecnt;
}

long long gcd(long long a, long long b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b) { long long t = b; b = a % b; a = t; }
    return a;
}

int main() {
    scanf("%d %d %lld", &N, &M, &K);
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
    }

    /* -------- Kosaraju Step 1: DFS on original graph, record finish order -------- */
    int stk_top = 0;
    for (int i = 1; i <= N; i++) {
        if (!vis[i]) {
            stk[stk_top] = i;
            stk_e[stk_top] = head[i];
            stk_top++;
            vis[i] = 1;
            while (stk_top > 0) {
                int u = stk[stk_top - 1];
                int e = stk_e[stk_top - 1];
                if (e) {
                    stk_e[stk_top - 1] = nxt[e];
                    int v = to_v[e];
                    if (!vis[v]) {
                        vis[v] = 1;
                        stk[stk_top] = v;
                        stk_e[stk_top] = head[v];
                        stk_top++;
                    }
                } else {
                    order_arr[ord_cnt++] = u;
                    stk_top--;
                }
            }
        }
    }

    /* -------- Kosaraju Step 2: DFS on reverse graph in reverse finish order -------- */
    for (int i = ord_cnt - 1; i >= 0; i--) {
        int start = order_arr[i];
        if (!comp[start]) {
            scc_cnt++;
            int c = scc_cnt;
            stk[0] = start;
            stk_e[0] = rhead[start];
            stk_top = 1;
            comp[start] = c;
            scc_size[c] = 1;
            scc_nxt[start] = scc_head[c];
            scc_head[c] = start;
            while (stk_top > 0) {
                int u = stk[stk_top - 1];
                int e = stk_e[stk_top - 1];
                if (e) {
                    stk_e[stk_top - 1] = rnxt[e];
                    int v = rto_v[e];
                    if (!comp[v]) {
                        comp[v] = c;
                        scc_size[c]++;
                        scc_nxt[v] = scc_head[c];
                        scc_head[c] = v;
                        stk[stk_top] = v;
                        stk_e[stk_top] = rhead[v];
                        stk_top++;
                    }
                } else {
                    stk_top--;
                }
            }
        }
    }

    /* -------- Check all vertices reachable from vertex 1 -------- */
    /* BFS/DFS from vertex 1 on original graph */
    memset(vis, 0, (N + 1) * sizeof(int));
    stk[0] = 1; stk_top = 1; vis[1] = 1;
    stk_e[0] = head[1];
    int reach_cnt = 1;
    while (stk_top > 0) {
        int u = stk[stk_top - 1];
        int e = stk_e[stk_top - 1];
        if (e) {
            stk_e[stk_top - 1] = nxt[e];
            int v = to_v[e];
            if (!vis[v]) {
                vis[v] = 1;
                reach_cnt++;
                stk[stk_top] = v;
                stk_e[stk_top] = head[v];
                stk_top++;
            }
        } else {
            stk_top--;
        }
    }
    if (reach_cnt < N) {
        printf("No\n");
        return 0;
    }

    /* -------- Compute cycle-gcd for each SCC -------- */
    /* dist[] is reused here: -1 = unvisited */
    memset(dist, -1, (N + 1) * sizeof(int));

    long long *scc_gcd_val = (long long *)calloc(scc_cnt + 1, sizeof(long long));

    for (int c = 1; c <= scc_cnt; c++) {
        if (scc_size[c] == 1) {
            scc_gcd_val[c] = 0; /* trivial: no cycle */
            continue;
        }
        /* BFS within SCC c */
        int root = scc_head[c];
        dist[root] = 0;
        int qh = 0, qt = 0;
        bfs_q[qt++] = root;
        long long g = 0;
        while (qh < qt) {
            int u = bfs_q[qh++];
            for (int e = head[u]; e; e = nxt[e]) {
                int v = to_v[e];
                if (comp[v] != c) continue; /* skip inter-SCC edges */
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    bfs_q[qt++] = v;
                }
                /* Cycle contribution: how much does this edge's back/cross
                   differ from a tree edge? */
                long long cyc = (long long)dist[u] + 1 - dist[v];
                if (cyc != 0) g = gcd(g, cyc);
            }
        }
        /* Reset dist for vertices in this SCC */
        for (int node = scc_head[c]; node; node = scc_nxt[node])
            dist[node] = -1;
        scc_gcd_val[c] = g;
    }

    /* -------- Check conditions -------- */

    /* Condition: SCC containing vertex 1 must have odd cycle-gcd > 0 */
    int c1 = comp[1];
    if (scc_gcd_val[c1] == 0 || scc_gcd_val[c1] % 2 == 0) {
        printf("No\n");
        free(scc_gcd_val);
        return 0;
    }

    /* Condition: every non-trivial SCC (reachable from 1, which is all of them
       since we checked reachability) must have odd cycle-gcd */
    for (int c = 1; c <= scc_cnt; c++) {
        if (scc_size[c] > 1 && scc_gcd_val[c] % 2 == 0) {
            printf("No\n");
            free(scc_gcd_val);
            return 0;
        }
    }

    printf("Yes\n");
    free(scc_gcd_val);
    return 0;
}