#include <stdio.h>
#include <stdlib.h>

int vertices;
int edgesCount;
int *edges;

#define getIndex(x, y) ((vertices) * (y) + (x))
#define getEl(x, y) (edges + getIndex((x), (y)))
#define getVal(x ,y) (*getEl((x), (y)))

void readMatrix(FILE *file) {
    fscanf(file, "%d\n", &vertices);
    edges = calloc((size_t) vertices * vertices, sizeof(int));
    edgesCount = 0;

    int first, second;
    while(-1 != fscanf(file, "%d %d\n", &first, &second)) {
        int *el = getEl(first, second);
        if (!*el) {
            *el = 1;
            getVal(second, first) = 1;
            ++edgesCount;
        }
    }

    return ;
}

int search(int *elements, int size, int what) {
    int i;
    for (i = 0; i < size; ++i) {
        if (what == elements[i]) {
            return i;
        }
    }
    return -1;
}

int checkCoherence(int excluded) {
    int visited[vertices];
    int i;
    for (i = 0; i < vertices; ++i) {
        visited[i] = 0;
    }
    visited[excluded] = 1;
    int stack[vertices * 2];
    stack[0] = visited[0] ? 1 : 0;
    int SP = 1;

    while (SP > 0) {
        int vertice = stack[--SP];
        int vToAdd;
        for (vToAdd = 0; vToAdd < vertices; ++vToAdd) {
            if (!getVal(vToAdd, vertice)) continue;
            if (-1 != search(stack, SP, vToAdd)) continue;
            if (visited[vToAdd]) continue;
            stack[SP++] = vToAdd;
        }
        visited[vertice] = 1;
    }

    for (i = 0; i < vertices; ++i) {
        if (!visited[i]) {
            return 0;
        }
    }

    return 1;
}

int checkTree(int excluded) {
    int excludedEdges = 0;
    int x;
    for (x = 0; x < vertices; ++x) {
        if (getVal(x, excluded)) ++excludedEdges;
    }
    return (edgesCount - excludedEdges + 1) == (vertices - 1);
}

int main() {
    FILE *file = fopen("input.txt", "rt");

    if (!file) {
        printf("Создайте файл `input.txt` такого формата:\n"
                       "```\n"
                       "Кол-во_вершин\n"
                       "Вершина1 Вершина2\n"
                       "...\n"
                       "БЕЗ переноса строки в конце```\n");
    }

     readMatrix(file);

    int excluded;
    for (excluded = 0; excluded < vertices; ++excluded) {
        printf("Vertice: %d\n", excluded);
        printf("    Coherence: %i\n", checkCoherence(excluded));
        printf("    Tree:      %i\n", checkTree(excluded));
        if (checkCoherence(excluded) && checkTree(excluded)) {
            printf("FIND! VERTICE: %d\n", excluded);
        }
    }

    return 0;
}