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 <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

/*
 * Koch Curve http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_C
 * 約10分
 * 実装例があったので頭がバグらずに済みました。複素数を使うと楽だと思います。
 */

template<typename M>
struct matrix {
    using T = typename M::T;
    int h, w;
    std::vector<std::vector<T>> data;
    matrix(int h, int w) : h(h), w(w), data(h, std::vector<T>(w, M::id_pl())) {}
    matrix(const std::vector<std::vector<T>> &src) : h(src.size()), w(src[0].size()), data(src) {}
    std::vector<T> &operator[](int i) { return data[i]; }
    const std::vector<T> &operator[](int i) const { return data[i]; }
    static matrix identity(int n) {
        matrix ret(n, n);
        for (int i = 0; i < n; i++) { ret[i][i] = M::id_cr(); }
        return ret;
    }
    bool operator==(const matrix &rhs) const {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (data[i][j] != rhs[i][j]) { return false; }
            }
        }
        return true;
    }
    bool operator!=(const matrix &rhs) const { return std::rel_ops::operator!=(*this, rhs); }
    matrix &operator+=(const matrix &rhs) {
        assert(h == rhs.h && w == rhs.w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                (*this)[i][j] = M::pl((*this)[i][j], rhs[i][j]);
            }
        }
        return *this;
    }
    matrix &operator-=(const matrix &rhs) {
        assert(h == rhs.h && w == rhs.w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                (*this)[i][j] = M::pl((*this)[i][j], M::inv_pl(rhs[i][j]));
            }
        }
        return *this;
    }
    matrix &operator*=(const matrix &rhs) {
        assert(w == rhs.h);
        std::vector<std::vector<T>> ret(h, std::vector<T>(rhs.w, M::id_pl()));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < rhs.w; j++) {
                for (int k = 0; k < w; k++) {
                    ret[i][j] = M::pl(ret[i][j], M::cr((*this)[i][k], rhs[k][j]));
                }
            }
        }
        data = ret;
        h = data.size(), w = data[0].size();
        return *this;
    }
    matrix &operator/=(const matrix &rhs) { return *this *= rhs.inv(); }
    matrix operator+() const { return *this; }
    matrix operator-() const { return matrix(h, w) -= (*this); }
    matrix operator+(const matrix &rhs) const { return matrix(*this) += rhs; }
    matrix operator-(const matrix &rhs) const { return matrix(*this) -= rhs; }
    matrix operator*(const matrix &rhs) const { return matrix(*this) *= rhs; }
    matrix operator/(const matrix &rhs) const { return matrix(*this) /= rhs; }
    matrix inv() const {
        assert(h == w);
        matrix id = identity(h);
        std::vector<std::vector<T>> ex(h, std::vector<T>(w << 1));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) { ex[i][j] = (*this)[i][j]; }
            for (int j = 0; j < w; j++) { ex[i][w + j] = id[i][j]; }
        }
        for (int i = 0; i < h; i++) {
            for (int j = i; j < w; j++) {
                if (!M::is_id_pl(ex[i][j])) {
                    swap(ex[i], ex[j]);
                    break;
                }
            }
            if (M::is_id_pl(ex[i][i])) { return matrix(0, 0); }
            T inv = M::inv_cr(ex[i][i]);
            for (int j = i + 1; j < w << 1; j++) { ex[i][j] = M::cr(ex[i][j], inv); }
            for (int j = i + 1; j < h; j++) {
                for (int k = i + 1; k < w << 1; k++) {
                    ex[j][k] = M::pl(ex[j][k], M::inv_pl(M::cr(ex[i][k], ex[j][i])));
                }
            }
        }
        for (int i = h - 1; i > 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                for (int k = w; k < w << 1; k++) {
                    ex[j][k] = M::pl(ex[j][k], M::inv_pl(M::cr(ex[i][k], ex[j][i])));
                }
            }
        }
        std::vector<std::vector<T>> ret(h, std::vector<T>(w));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                ret[i][j] = ex[i][w + j];
            }
        }
        return ret;
    }
    matrix pow(long long n) const {
        assert(h == w);
        matrix ret = identity(h), mul = *this;
        while (n > 0) {
            if (n & 1) { ret *= mul; }
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend std::ostream &operator<<(std::ostream &os, const matrix &rhs) {
        for (int i = 0; i < rhs.h; i++) {
            os << "[";
            for (int j = 0; j < rhs.w; j++) {
                os << rhs[i][j] << (j + 1 == rhs.w ? "]\n" : ",");
            }
        }
        return os;
    }
};

struct bool_mat {
    using T = bool;
    static T pl(const T &a, const T &b) { return a | b; }
    static T cr(const T &a, const T &b) { return a & b; }
    static T id_pl() { return 0; }
    static T id_cr() { return 1; }
    static T inv_pl(const T &a) { return 0; } // 本当はない
    static T inv_cr(const T &a) { return 0; } // 本当はない
    static bool is_id_pl(const T &a) { return a == 0; };
};

// Can I go there? 実装中
// 辺ベースでbool値の行列累乗をすればいけるはず

void solve(int N, int M, int Z) {
    vint s(M), d(M);
    vvint edx(N);
    vint rev(2 * M), to(2 * M);
    rep(i, M) {
        cin >> s[i] >> d[i];
        s[i]--, d[i]--;
        edx[s[i]].push_back(2 * i + 0), rev[2 * i + 0] = 2 * i + 1, to[2 * i + 0] = d[i];
        edx[d[i]].push_back(2 * i + 1), rev[2 * i + 1] = 2 * i + 0, to[2 * i + 1] = s[i];
    }
    matrix<bool_mat> a(M * 2 + 1, M * 2 + 1), b(M * 2 + 1, 1);
    b[M * 2][0] = 1;
    rep(i, edx[0].size()) { a[edx[0][i]][M * 2] = 1; }
    rep(i, M * 2) {
        int t = to[i];
        rep(j, edx[t].size()) { a[edx[t][j]][i] = 1; }
        a[rev[i]][i] = 0;
    }
    b = a.pow(Z) * b;
    bool ans = false;
    rep(i, M * 2) {
        if (to[i] == N - 1 && b[i][0]) { ans = true; }
    }
    if (ans) { cout << "yes" << endl; }
    else { cout << "no" << endl; }
}
signed main() {
    while (true) {
        int N, M, Z;
        cin >> N >> M >> Z;
        if (N == 0 && M == 0 && Z == 0) { break; }
        solve(N, M, Z);
    }
}
