#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<vector<int>> g;
vector<int> color;
bool valid(int v) {
    for (int i = 0; i < g[v].size(); i++) {
        if (color[g[v][i]] == color[v]) {
            return false;
        }

    }
    return true;
}
void coloring( int v, int c) {
    //c = 0;
    if (v == n) {
        cout << "YES";
        exit(0);
    }
    else {
        for (int i = 0; i < c; i++) {
            color[v] = i;
            if (valid(v) == true) {
                coloring( v + 1, c);
            }
                color[v] = 0;
        }
    }
}


int main() {
    int m, c;
    cin >> n >> m >> c;
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int s, f;
        cin >> s >> f;
        s--;
        f--;
        g[s].push_back(f);
        g[f].push_back(s);

    }
    color.resize(n, -1);
    coloring( 0, c);
    cout << "NO";
}