#include <cstdio>
#include <cstdlib>
#include <vector>
#include "game.h"

namespace {

    int read_int() {
        int x;
        if (scanf("%d", &x) != 1) {
            fprintf(stderr, "Error while reading input\n");
            exit(1);
        }
        return x;
    }

}  // namespace

int main() {
    int N = read_int();
    int M = read_int();
    int K = read_int();
    std::vector<int> u(M), v(M);
    for (int i = 0; i < M; ++i) {
        u[i] = read_int();
        v[i] = read_int();
    }

    init(N, K);
    int i;
    for (i = 0; i < M; ++i) {
        int answer = add_teleporter(u[i], v[i]);
        if (answer != 0 && answer != 1) {
            i = -1;
            break;
        } else if (answer == 1) {
            break;
        }
    }
    printf("%d\n", i);
    return 0;
}

/usr/bin/ld: /tmp/cceCtBAa.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cc1OH0qc.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cceCtBAa.o: in function `main':
answer.code:(.text.startup+0xfc): undefined reference to `init(int, int)'
/usr/bin/ld: answer.code:(.text.startup+0x11f): undefined reference to `add_teleporter(int, int)'
/usr/bin/ld: answer.code:(.text.startup+0x188): undefined reference to `init(int, int)'
/usr/bin/ld: /tmp/cc1OH0qc.o: in function `main':
implementer.cpp:(.text.startup+0x58): undefined reference to `init(int, int)'
/usr/bin/ld: implementer.cpp:(.text.startup+0xc2): undefined reference to `add_teleporter(int, int)'
collect2: error: ld returned 1 exit status