// Verificador del laboratorio: verificador caso.in caso.out salida
// Termina con 0 si la salida es correcta. Cuando el primer jugador gana puede haber varias
// primeras jugadas ganadoras: se acepta cualquiera, y se comprueba que de verdad gana.
#include <cstddef>
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

struct Graph {
    std::vector<std::string> nodes;
    std::vector<std::vector<int>> edges;
    int start = 0;
};

static Graph read_graph(std::istream& in, std::map<std::string, int>& index) {
    Graph g;
    bool in_edges = false;
    std::string line;
    while (std::getline(in, line)) {
        if (line.empty() || line[0] == '#') {
            continue;
        }
        std::istringstream words(line);
        std::string first;
        std::string second;
        if (!(words >> first)) {
            continue;
        }
        if (in_edges) {
            words >> second;
            g.edges[index[first]].push_back(index[second]);
        } else if (first == "nodes:") {
            while (words >> second) {
                index[second] = static_cast<int>(g.nodes.size());
                g.nodes.push_back(second);
            }
            g.edges.assign(g.nodes.size(), {});
        } else if (first == "start:") {
            words >> second;
            g.start = index[second];
        } else if (first == "edges:") {
            in_edges = true;
        }
    }
    return g;
}

// ¿Gana quien debe mover con la ficha en current?
static bool mover_wins(const Graph& g, int current, std::vector<char>& visited) {
    for (int next : g.edges[current]) {
        if (visited[next]) {
            continue;
        }
        visited[next] = 1;
        bool rival_wins = mover_wins(g, next, visited);
        visited[next] = 0;
        if (!rival_wins) {
            return true;
        }
    }
    return false;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cout << "uso: verificador caso.in caso.out salida\n";
        return 2;
    }
    std::ifstream input(argv[1]);
    std::ifstream expected(argv[2]);
    std::ifstream output(argv[3]);
    std::map<std::string, int> index;
    Graph g = read_graph(input, index);

    std::string want;
    expected >> want;
    std::vector<std::string> got;
    std::string word;
    while (output >> word) {
        got.push_back(word);
    }
    if (got.empty()) {
        std::cout << "la salida está vacía\n";
        return 1;
    }
    if (got[0] != "gana" && got[0] != "pierde") {
        std::cout << "la primera palabra debe ser gana o pierde, y salió " << got[0] << '\n';
        return 1;
    }
    if (got[0] != want) {
        std::cout << "esperaba " << want << ", salió " << got[0] << '\n';
        return 1;
    }
    if (want == "pierde") {
        if (got.size() != 1) {
            std::cout << "después de pierde no va nada\n";
            return 1;
        }
        return 0;
    }
    if (got.size() != 2) {
        std::cout << "después de gana va un nodo, y nada más\n";
        return 1;
    }
    if (index.count(got[1]) == 0) {
        std::cout << got[1] << " no es un nodo del grafo\n";
        return 1;
    }
    int move = index[got[1]];
    bool is_edge = false;
    for (int next : g.edges[g.start]) {
        is_edge = is_edge || next == move;
    }
    if (!is_edge || move == g.start) {
        std::cout << "no hay jugada de " << g.nodes[g.start] << " a " << got[1] << '\n';
        return 1;
    }
    std::vector<char> visited(g.nodes.size(), 0);
    visited[g.start] = 1;
    visited[move] = 1;
    if (mover_wins(g, move, visited)) {
        std::cout << "la jugada " << got[1] << " no es ganadora: el rival tiene una respuesta que gana\n";
        return 1;
    }
    return 0;
}
