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 <cassert>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

constexpr double eps = 1e-8;

namespace detail {

bool is_zero(double d) {
    return (std::abs(d) < eps);
}
bool is_zero(long double d) {
    return (std::abs(d) < eps);
}

}

template <typename T>
class matrix {
public:
    matrix() = delete;
    matrix(int r, int c) 
        : v_(r, std::vector<T>(c)),
          row_(r),
          column_(c)
    {}
    matrix(std::vector<std::vector<T>> const& v)
        : v_(v),
          row_(v.size()),
          column_((v.size() == 0 ? 0 : v[0].size()))
    {}
    matrix(matrix const&) = default;
    matrix(matrix&&) = default;
    matrix& operator=(matrix const&) = default;
    matrix& operator=(matrix&&) = default;
    ~matrix() = default;

    std::vector<T>& operator[](unsigned int i) {
        return v_[i];
    }
    const std::vector<T>& operator[](unsigned int i) const {
        return v_[i];
    }
    matrix& operator+=(matrix const& other) {
        assert("matrix operator+: row or column size does not match" && other.row_size() == row_ && other.column_size() == column_);

        for(int i=0; i<row_; ++i) {
            for(int j=0; j<column_; ++j) {
                v_[i][j] += other[i][j];
            }
        }
        return *this;
    }
    matrix& operator-=(matrix const& other) {
        assert("matrix operator-: row or column size does not match" && other.row_size() == row_ && other.column_size() == column_);

        for(int i=0; i<row_; ++i) {
            for(int j=0; j<column_; ++j) {
                v_[i][j] -= other[i][j];
            }
        }
        return *this;
    }

    int row_size() const {
        return row_;
    }
    int column_size() const {
        return column_;
    }

    // for debug
    void print() {
        for(int i=0; i<row_; ++i) {
            for(int j=0; j<column_; ++j) {
                std::cout << v_[i][j];
                if(j != column_ - 1) {
                    std::cout << " ";
                }
            }
            std::cout << std::endl;
        }
    }

private:
    std::vector<std::vector<T>> v_;
    int row_, column_;
};

template <typename T>
matrix<T> operator-(matrix<T> m) {
    for(int i=0; i<m.row_size(); ++i) {
        for(int j=0; j<m.column_size(); ++j) {
            m[i][j] = -m[i][j];
        }
    }
}

template <typename T>
matrix<T> operator+(matrix<T> lhs, matrix<T> const& rhs) {
    lhs += rhs;
    return lhs;
}

template <typename T>
matrix<T> operator-(matrix<T> lhs, matrix<T> const& rhs) {
    lhs -= rhs;
    return lhs;
}

template <typename T>
matrix <T> operator*(matrix<T> const& lhs, matrix<T> const& rhs) {
    assert("matrix operator*: lhs.column_size() != rhs.row_size()" && lhs.column_size() == rhs.row_size());

    matrix<T> ret(lhs.row_size(), rhs.column_size());
    for(int i=0; i<ret.row_size(); ++i) {
        for(int k=0; k<lhs.column_size(); ++k) {
            for(int j=0; j<ret.column_size(); ++j) {
                ret[i][j] += lhs[i][k] * rhs[k][j];
            }
        }
    }
    return ret;
}

template <typename T>
matrix<T> transpose(matrix<T> const& m) {
    const int R = m.row_size(), C = m.column_size();
    matrix<T> ret(C, R);
    for(int i=0; i<C; ++i) {
        for(int j=0; j<R; ++j) {
            ret[i][j] = m[j][i];
        }
    }
    return ret;
}

// verified: AOJ2564
template <typename T>
int rank_matrix(matrix<T> a) {
    const int r = a.row_size(), c = a.column_size();
    matrix<long double> b(r, c);
    for(int i=0; i<r; ++i) {
        for(int j=0; j<c; ++j) {
            b[i][j] = static_cast<long double>(a[i][j]);
        }
    }
    return rank_matrix<long double>(std::move(b));
}

template <>
int rank_matrix(matrix<long double> a) {
    const int R = a.row_size(), C = a.column_size();
    int r = 0;
    for(int i=0; i<C && r < R; ++i) {
        int pivot = r;
        for(int j=r+1; j<R; ++j) {
            if(std::abs(a[j][i]) > std::abs(a[pivot][i])) {
                pivot = j;
            }
        }
        std::swap(a[pivot], a[r]);
        if(detail::is_zero(a[r][i])) {
            continue;
        }
        for(int k=C-1; k>=i; --k) {
            a[r][k] = a[r][k] / a[r][i];
        }
        for(int j=r+1; j<R; ++j) {
            for(int k=C-1; k>=i; --k) {
                a[j][k] += -a[r][k] * a[j][i];
            }
        }
        ++r;
    }
    return r;
}

// todo: only long double?
template <typename T>
T det(matrix<T> a) {
    const int R = a.row_size(), C = a.column_size();
    matrix<long double> b(R, C);
    for(int i=0; i<R; ++i) {
        for(int j=0; j<C; ++j) {
            b[i][j] = static_cast<long double>(a[i][j]);
        }
    }
    return static_cast<T>(det<long double>(std::move(b)));
}
template <>
long double det(matrix<long double> a) {
    assert("det(): matrix is not square." && a.column_size() == a.row_size());
    const int R = a.row_size(), C = a.column_size();
    long double ret = 1.0;
    for(int i=0; i<R; ++i) {
        int pivot = i;
        for(int j=i+1; j<R; ++j) {
            if(std::abs(a[j][i]) > std::abs(a[pivot][i])) {
                pivot = j;
            }
        }
        std::swap(a[pivot], a[i]);
        ret *= a[i][i] * (i != pivot ? -1.0 : 1.0);
        if(detail::is_zero(a[i][i])) {
            break;
        }
        for(int j=i+1; j<R; ++j) {
            for(int k=C-1; k>=i; --k) {
                a[j][k] -= a[i][k] * a[j][i] / a[i][i];
            }
        }
    }
    return ret;
}

template <typename T>
matrix<T> make_identity_matrix(int n) {
    matrix<T> ret(n, n);
    for(int i=0; i<n; ++i) {
        ret[i][i] = 1;
    }
    return ret;
}

// mulptile mod ver
template <typename T>
matrix<T> mul(matrix<T> const& a, matrix<T> const& b, long long M) {
    int R = a.row_size(), C = b.column_size();
    assert("matrix mul: row and column size does not match" && a.column_size() == b.row_size());
    matrix<T> ret(R, C);
    for(int i=0; i<R; ++i) {
        for(int k=0; k<a.column_size(); ++k) {
            for(int j=0; j<C; ++j) {
                ret[i][j] = (ret[i][j] + ((a[i][k] * b[k][j]) % M)) % M;
            }
        }
    }
    return ret;
}

template <typename T>
matrix<T> pow(matrix<T> x, long long y) {
    assert("matrix pow: matrix is not square" && x.column_size() == x.row_size());
    matrix<T> ret = make_identity_matrix<T>(x.column_size());
    while(y > 0) {
        if(y & 1) {
            ret = ret * x;
        }
        x = x * x;
        y >>= 1;
    }
    return ret;
}

template <typename T>
matrix<T> modpow(matrix<T> x, long long y, long long M) {
    assert("matrix pow: matrix is not square" && x.column_size() == x.row_size());
    matrix<T> ret = make_identity_matrix<T>(x.column_size());
    while(y > 0) {
        if(y & 1) {
            ret = mul(ret, x, M);
        }
        x = mul(x, x, M);
        y >>= 1;
    }
    return ret;
}



// LUP factorization(gauss)
// verified: AOJ1328
// Ax = b
// note: A must be regular(non-singular)
// return: x
//         or size 0 vector (if x does not exist or not unique)
vector<double> gauss_jordan(matrix<double>& A, std::vector<double> const& b) {
    int n = A.row_size();
    matrix<double> B(n, n+1);
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            B[i][j] = A[i][j];
        }
    }
    for(int i=0; i<n; ++i) {
        B[i][n] = b[i];
    }

    for(int i=0; i<n; ++i) {
        int pivot = i;
        for(int j=i; j<n; ++j) {
            if(std::abs(B[j][i]) > std::abs(B[pivot][i])) {
                pivot = j;
            }
        }
        std::swap(B[i], B[pivot]);
        if(std::abs(B[i][i]) < eps) {
            return std::vector<double>();
        }

        for(int j=i+1; j<=n; ++j) {
            B[i][j] /= B[i][i];
        }
        for(int j=0; j<n; ++j) {
            if(i != j) {
                for(int k=i+1; k<=n; ++k) {
                    B[j][k] -= B[j][i] * B[i][k];
                }
            }
        }
    }

    std::vector<double> x(n);
    for(int i=0; i<n; ++i) {
        x[i] = B[i][n];
    }
    return x;
}


using P = pair<int, int>;
using ll = long long;

int main() {
    int N, M, Z;
    while(cin >> N >> M >> Z, N) {
        vector<P> node; // (current, prev)
        node.push_back(make_pair(1, 0));
        for(int i=0; i<M; ++i) {
            int s, d;
            cin >> s >> d;
            node.push_back(make_pair(s, d));
            node.push_back(make_pair(d, s));
        }
        matrix<ll> m(node.size(), node.size());
        for(int i=0; i<node.size(); ++i) {
            int current = node[i].first;
            int prev = node[i].second;
            for(int j=0; j<node.size(); ++j) {
                if(i != j) {
                    int next_current = node[j].first;
                    int next_prev = node[j].second;
                    if(current == next_current || next_current == prev) {
                        continue;
                    }
                    if(current == next_prev) {
                        m[i][j] = 1;
                    }
                }
            }
        }
        m = pow(m, Z);
        bool ok = false;
        for(int i=0; i<node.size(); ++i) {
            if(node[i].first == N && m[0][i] != 0) {
                ok = true;
            }
        }
        if(ok) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
}
