At one point, there was a president who traveled around Japan to do business. One day he got a mysterious ticket. If you use the ticket, the train fare will be free regardless of the distance to the destination. However, when moving from the current station to the adjacent station is counted as one step, if the number of steps to move is not exactly equal to the number written on the ticket, an additional fee will be charged. It is forbidden to move around a section immediately, but it is permissible to go through a station or section that you have already visited multiple times. For example, you cannot move to station 1, station 2, or station 1, but there is no problem with moving to station 1, station 2, station 3, station 1, or station 2. Also, if you finally arrive at your destination, you may go through the starting point and destination as many times as you like.

The president immediately decided to use this ticket to go to his next destination. However, since the route map is complicated, the route cannot be easily determined. Your job is to write a program on behalf of the president to determine if you can reach your destination for free.

Stations are numbered from 1 to N, with the departure station being 1 and the destination station being N. The route map is given by the row of sections connecting the two stations. The section can pass in either direction. It is guaranteed that there is no section connecting the same stations and that there is at most one section connecting a pair of stations.



Input

The input consists of multiple datasets.

Each dataset is given in the following format.

N M Z
s1 d1
s2 d2
...
sM dM

N is the total number of stations, M is the total number of sections, and Z is the number of steps written on the ticket. si and di (1 ≤ i ≤ M) are integers representing station numbers, indicating that there is an interval between station si and station di, respectively.

N, M, Z are positive integers and satisfy the following conditions: 2 ≤ N ≤ 50, 1 ≤ M ≤ 50, 0 <Z <231.

After the last dataset, there is a line that says "` 0 0 0 `".

The number of datasets does not exceed 30.

Output

For each dataset, output a one-line string containing only "` yes` "if the destination can be reached with just the number of steps written on the ticket, or" `no`" if not. ..

Example

Input

2 1 1
1 2
2 1 2
1 2
3 1 2
1 2
8 8 5778
1 2
2 3
2 4
3 5
5 6
6 7
7 8
4 8
8 8 5777
1 2
2 3
2 4
3 5
5 6
6 7
7 8
4 8
0 0 0


Output

yes
no
no
yes
no
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
//cin.sync_with_stdio(false);
//streambuf
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using ti3 = tuple<int, int, int>;
using vti3 = vector<ti3>;
template<class T, int s>using va = vector<array<T, s>>;
template<class T, class T2> using umap = unordered_map<T, T2>;
template<class T> using uset = unordered_set<T>;
template<class T> void cmin(T &a, const T&&b) { if (a > b)a = b; }
template<class T> void cmax(T &a, const T&&b) { if (a < b)a = b; }
#define ALL(a) a.begin(),a.end()
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a) for(int i=1;i<=a;i++)
const ll mod = 1000000007;
#ifndef INT_MAX
const int INT_MAX = numeric_limits<signed>().max();
#endif
template<class T>using heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>using pque = priority_queue<T, vector<T>, function<T(T, T)>>;
template <class T>
inline void hash_combine(size_t & seed, const T & v) {
	hash<T> hasher;
	seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
namespace std {

	template<typename S, typename T> struct hash<pair<S, T>> {
		inline size_t operator()(const pair<S, T> & v) const {
			size_t seed = 0;
			hash_combine(seed, v.first);
			hash_combine(seed, v.second);
			return seed;
		}
	};
	// Recursive template code derived from Matthieu M.
	template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
	struct HashValueImpl
	{
		static void apply(size_t& seed, Tuple const& tuple)
		{
			HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
			hash_combine(seed, std::get<Index>(tuple));
		}
	};

	template <class Tuple>
	struct HashValueImpl<Tuple, 0>
	{
		static void apply(size_t& seed, Tuple const& tuple)
		{
			hash_combine(seed, std::get<0>(tuple));
		}
	};

	template <typename ... TT>
	struct hash<std::tuple<TT...>>
	{
		size_t
			operator()(std::tuple<TT...> const& tt) const
		{
			size_t seed = 0;
			HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
			return seed;
		}

	};
}
ull pow(ull base, ull i, ull mod) {
	ull a = 1;
	while (i) {
		if (i & 1) {
			a *= base;
			a %= mod;
		}
		base *= base;
		base %= mod;
		i /= 2;
	}
	return a;
}
class unionfind {
	vector<int> par, rank, size_;//????????§??????????????¢???????????????????????????rank???????????????size?????????
public:
	unionfind(int n) :par(n), rank(n), size_(n, 1) {
		iota(ALL(par), 0);
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y)return;
		if (rank[x] < rank[y])swap(x, y);
		par[y] = x;
		size_[x] += size_[y];
		if (rank[x] == rank[y])rank[x]++;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return size_[find(x)];
	}
};
ll gcd(ll a, ll b) {
	while (b) {
		ll c = a%b;
		a = b;
		b = c;
	}
	return a;
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b)*b;
}
int popcnt(unsigned long long a) {
	a = (a & 0x5555555555555555) + (a >> 1 & 0x5555555555555555);
	a = (a & 0x3333333333333333) + (a >> 2 & 0x3333333333333333);
	a = (a & 0x0f0f0f0f0f0f0f0f) + (a >> 4 & 0x0f0f0f0f0f0f0f0f);
	a = (a & 0x00ff00ff00ff00ff) + (a >> 8 & 0x00ff00ff00ff00ff);
	a = (a & 0x0000ffff0000ffff) + (a >> 16 & 0x0000ffff0000ffff);
	return (a & 0xffffffff) + (a >> 32);
}
template<class T, class Func = function<T(T, T)>>
class segtree {
	vector<T> obj;
	int offset;
	Func updater;
	T e;
	int bufsize(int num) {
		int i = 1;
		for (; num >i; i <<= 1);
		offset = i - 1;
		return (i << 1) - 1;
	}
	T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)return e;
		if (a <= l && r <= b)return obj[k];
		else return updater(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
	}
public:
	T query(int a, int b) {//[a,b)
		return query(a, b, 0, 0, offset + 1);
	}
	void updateall(int l = 0, int r = -1) {
		if (r < 0)r = offset;
		l += offset, r += offset;
		do {
			l = l - 1 >> 1, r = r - 1 >> 1;
			for (int i = l; i < r; i++)obj[i] = updater(obj[i * 2 + 1], obj[i * 2 + 2]);
		} while (r);
	}
	void update(int k, T &a) {
		k += offset;
		obj[k] = a;
		while (k) {
			k = k - 1 >> 1;
			obj[k] = updater(obj[k * 2 + 1], obj[k * 2 + 2]);
		}
	}
	segtree(int n, T e, const Func &updater_ = Func()) :obj(bufsize(n), e), e(e), updater(updater_) {}
	segtree(vector<T> &vec, T e, const Func &updater = Func()) :obj(bufsize(vec.size()), e), e(e), updater(updater) {
		copy(vec.begin(), vec.end(), obj.begin() + offset);
		updateall();
	}
	typename vector<T>::reference operator[](int n) {
		return obj[n + offset];
	}
};
template<class T>
class matrix {
	vector<vector<T>> obj;
	pair<int, int> s;
public:
	matrix(pair<int, int> size, T e = 0) :matrix(size.first, size.second, e) {}
	matrix(int n, int m = -1, T e = 0) :obj(n, vector<T>(m == -1 ? n : m, e)), s(n, m == -1 ? n : m) {}
	static matrix e(int n) {
		matrix a = (n);
		for (int i = 0; i < n; i++)a[i][i] = 1;
		return a;
	}
	matrix& operator+=(const matrix &p) {
		if (s != p.s)throw runtime_error("matrix error");
		for (int i = 0; i < s.first; i++)
			for (int j = 0; j < s.second; j++)obj[i][j] += p.obj[i][j];
		return *this;
	}
	matrix operator+(const matrix &p) {
		matrix res(*this);
		return res += p;
	}
	matrix& operator-=(const matrix &p) {
		if (s != p.s)throw runtime_error("matrix error");
		for (int i = 0; i < s.first; i++)
			for (int j = 0; j < s.second; j++)obj[i][j] -= p.obj[i][j];
		return *this;
	}
	matrix operator-(const matrix &p) {
		matrix res(*this);
		return res -= p;
	}
	matrix& operator*=(T p) {
		for (auto &a : obj)
			for (auto &b : a)b *= p;
		return *this;
	}
	matrix operator*(T p) {
		matrix res(*this);
		return res *= p;
	}
	matrix operator*(const matrix &p) {
		if (s.second != p.s.first)throw runtime_error("matrix error");
		matrix ret(s.first, p.s.second);
		for (int i = 0; i < s.first; i++)
			for (int j = 0; j < s.second; j++)
				for (int k = 0; k < p.s.second; k++)ret[i][k] += obj[i][j] * p.obj[j][k];
		return ret;
	}
	matrix &operator*=(const matrix &p) {
		return *this = *this*p;
	}
	pair<int, int> size() const {
		return s;
	}
	matrix &mod(T m) {
		if (m < 0)
			for (auto &a : obj)
				for (auto &b : a)b = (b ? 1 : 0);
		else for (auto &a : obj)
			for (auto &b : a)b %= m;
		return *this;
	}
	typename vector<vector<T>>::reference operator[](int t) {
		return obj[t];
	}
};
template<class T> inline
matrix<T> pow(matrix<T> &base, unsigned exp) {
	auto base_(base);
	if (base_.size().first != base_.size().second)throw runtime_error("matrix error");
	matrix<T> res = matrix<T>::e(base_.size().first);
	for (;;) {
		if (exp & 1)res *= base_;
		if (!(exp /= 2))break;
		base_ *= base_;
	}
	return res;
}
template<class T> inline
matrix<T> modpow(matrix<T> &base, unsigned exp, T m) {
	auto base_(base);
	if (base.size().first != base_.size().second)throw runtime_error("matrix error");
	matrix<T> res = matrix<T>::e(base_.size().first);
	for (;;) {
		if (exp & 1)(res *= base_).mod(m);
		if (!(exp /= 2))break;
		(base_ *= base_).mod(m);
	}
	return res;
}
template<class T>int id(vector<T> &a, T b) {
	return lower_bound(ALL(a), b) - a.begin();
}
class Flow {
	int V;
	struct edge { int to, cap, rev, cost; };
	vector<vector<edge>> G;
	vector<int> level, iter, h, dist, prevv, preve;
	Flow(int size) :G(size + 1), V(size + 1) {
	}
	void add_edge(int from, int to, int cap, int cost = 0) {
		G[from].push_back(edge{ to, cap, (int)G[to].size(),cost });
		G[to].push_back(edge{ from,0,(int)G[from].size() - 1,-cost });
	}
	void bfs(int s) {
		fill(level.begin(), level.end(), -1);
		queue<int> que;
		level[s] = 0;
		que.push(s);
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (int i = 0; i < G[v].size(); i++) {
				edge &e = G[v][i];
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					que.push(e.to);
				}
			}
		}
	}
	int dfs(int v, int t, int f) {
		if (v == t)return f;
		for (int &i = iter[v]; i < G[v].size(); i++) {
			edge &e = G[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	int max_flow(int s, int t) {
		level.resize(V);
		iter.resize(V);
		int flow = 0;
		for (;;) {
			bfs(s);
			if (level[t] < 0)return flow;
			fill(iter.begin(), iter.end(), 0);
			int f;
			while ((f = dfs(s, t, numeric_limits<int>::max()))>0) {
				flow += f;
			}
		}
	}
	typedef pair<int, int> P;
	int min_cost_flow(int s, int t, int f) {
		int res = 0;
		h.resize(V);
		dist.resize(V);
		prevv.resize(V);
		preve.resize(V);
		fill(h.begin(), h.end(), 0);
		while (f > 0) {
			priority_queue<P, vector<P>, greater<P>> que;
			fill(dist.begin(), dist.end(), numeric_limits<int>::max());
			dist[s] = 0;
			que.push({ 0,s });
			while (!que.empty()) {
				P p = que.top(); que.pop();
				int v = p.second;
				if (dist[v] < p.first)continue;
				for (int i = 0; i < G[v].size(); i++) {
					edge &e = G[v][i];
					if (e.cap > 0 && dist[e.to]>dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						que.push({ dist[e.to],e.to });
					}
				}
			}
			if (dist[t] == numeric_limits<int>::max()) {
				return -1;
			}
			for (int v = 0; v < V; v++)h[v] += dist[v];

			int d = f;
			for (int v = t; v != s; v = prevv[v]) {
				d = min(d, G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d*h[t];
			for (int v = t; v != s; v = prevv[v]) {
				edge &e = G[prevv[v]][preve[v]];
				e.cap -= d;
				G[v][e.rev].cap += d;
			}
		}
		return res;
	}
};

// Suffix Array	?????????O(|S|log^2|S|), ????´¢O(|T|log|S|), ?????????????§????O(|S|)
class StringSearch {
	const int n;
	string S;
public:
	vector<int> sa, rank;
	StringSearch(const string &S_)
		: n(S_.size()), S(S_), sa(n + 1), rank(n + 1)
	{
		for (int i = 0; i <= n; i++) {
			sa[i] = i;
			rank[i] = i < n ? S[i] : -1;
		}

		vector<int> tmp(n + 1);
		for (int k = 1; k <= n; k *= 2) {
			auto Compare_SA = [=](int i, int j) {
				if (this->rank[i] != this->rank[j]) return this->rank[i] < this->rank[j];

				int ri = i + k <= n ? this->rank[i + k] : -1;
				int rj = j + k <= n ? this->rank[j + k] : -1;
				return ri < rj;
			};
			sort(sa.begin(), sa.end(), Compare_SA);

			tmp[sa[0]] = 0;
			for (int i = 1; i <= n; i++) {
				tmp[sa[i]] = tmp[sa[i - 1]] + (Compare_SA(sa[i - 1], sa[i]) ? 1 : 0);
			}
			for (int i = 0; i <= n; i++) {
				this->rank[i] = tmp[i];
			}
		}
	}

	bool Contain(const string &T) {
		int a = 0, b = n;
		while (b - a > 1) {
			int c = (a + b) / 2;
			if (S.compare(sa[c], T.length(), T) < 0) a = c;
			else b = c;
		}
		return S.compare(sa[b], T.length(), T) == 0;
	}

	vector<int> LCPArray() {
		for (int i = 0; i <= n; i++) rank[sa[i]] = i;

		int h = 0;
		vector<int> lcp(n + 1);
		for (int i = 0; i < n; i++) {
			int j = sa[rank[i] - 1];

			if (h > 0) h--;
			for (; j + h < n && i + h < n; h++) {
				if (S[j + h] != S[i + h]) break;
			}
			lcp[rank[i] - 1] = h;
		}
		return lcp;
	}
};
int main() {
	int n, m, z;
	while (cin >> n >> m >> z, n) {
		m++;
		n++;
		vpii w(m);
		w[0] = { 0,1 };
		vector<vi> v(n);
		matrix<int> a(2 * m);
		rep1(i, m-1) {
			int s, d;
			cin >> s >> d;
			v[s].push_back(d);
			v[d].push_back(s);
			w[i] = { s,d };
		}
		rep(i, m) {
			int s = w[i].first, d = w[i].second;
			rep(j,m){
				if (w[j].first == d&&w[j].second != s)a[j * 2 + 1][i * 2+1] = 1;
				if (w[j].first != s&&w[j].second == d)a[j * 2][i * 2+1] = 1;
			}
			swap(s, d);
			rep(j, m) {
				if (w[j].first == d&&w[j].second != s)a[j * 2 + 1][i * 2] = 1;
				if (w[j].first != s&&w[j].second == d)a[j * 2][i * 2] = 1;
			}
		}
		matrix<int> u(m * 2, 1);
		u[1][0] = 1;
		bool f = 0;
		a = modpow(a, z, -1)*u;
		rep(i, m) {
			if (w[i].first == n-1)f += a[i * 2][0];
			if (w[i].second == n-1)f += a[i * 2+1][0];
		}
		cout << (f ? "yes" : "no") << endl;
	}
}