#include <bits/stdc++.h>
#include <algorithm>
#define int long long

using namespace std;

inline int read () {
	int w = 0, f = 1; char ch = getchar ();
	while (ch < '0' || ch > '9') {if (ch == '-')f = -1;ch = getchar ();}
	while (ch >= '0' && ch <= '9') {w = (w << 3) + (w << 1) + ch - '0';ch = getchar ();}
	return f * w;
}
int n, m, k;
struct Graph {
	vector <int> E[10005];
	int rd[10005];
	void push (int x, int y) {
		E[x].push_back (y);
		rd[y]++;
	}
	bool tuopu () {
		queue <int> Q;
		for (int i = 1; i <= m; i++) {
			if (rd[i] == 0) {
				Q.push (i);
			}
		}
		int cnt = 0;
		while (Q.size ()) {
			int nw = Q.front ();
			Q.pop ();
			cnt++;
			for (int i = 0; i < E[nw].size (); i++) {
				rd[E[nw][i]]--;
				if (rd[E[nw][i]] == 0) {
					Q.push (E[nw][i]);
				}
			}
		}
		
		return cnt != m ? 1 : 0;
	}
}G;
int ksm (int a, int b, int p) {
	int ans = 1;
	while (b) {
		if (b & 1) {
			ans = ans * a % p;	
		}
		a *= a;
		b >>= 1;
	}
	return ans;
}
signed main () {
	int x, y;
	n = read (), m = read (), k = read ();
	for (int i = 1; i <= m; i++) {
		x = read (), y = read ();
		G.push (x, y);		
	}
	
	if (G.tuopu ()) {	//有环 
		puts ("No");
		cout << k * k << "\n"; 
	}
	else {
		puts ("Yes");
		cout << ksm (2ll, k, 9997ll);
	}
	return 0;
}

用的是拓扑排序。