// вторая лабораторная
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct Node{
    Node(string name, T mark) : name(std::move(name)), mark(std::move(mark)) {}

    vector<pair<long long int, Node*> > vc;

    string name;

    T mark;
};

template<typename T>
struct Graph {

    long long int first(Node<T>*& node) {
        if (node->vc.empty())
            return -1;
        return node_to_index[node->vc[0].second];
    }

    long long int next(Node<T>*& node, long long int index) {
        long long int i = 0;
        for (; i < node->vc.size(); ++i) {
            if (node_to_index[node->vc[i].second] == index)
                break;
        }
        if (i < node->vc.size())
            return node_to_index[node->vc[i].second];
        return -1;
    }

    Node<T>* vertex(Node<T>*& node, long long int index) {
        if (index < 0)
            return nullptr;
        for (long long int i = 0; i < node->vc.size(); ++i) {
            if (node_to_index[node->vc[i].second] == index)
                return node->vc[i].second;
        }
        return nullptr;
    }

    void add_v(string name, T mark) {
        nodes.push_back(new Node(std::move(name), std::move(mark)));
        node_to_index[nodes.back()] = nodes.size() - 1;
    }

    void add_e(Node<T>* first, Node<T>* second, long long int weight, bool is_oriented=true) {
        first->vc.push_back({weight, second});
        if (!is_oriented)
            second->vc.push_back({weight, first});
    }

    void del_v(string name) {
        Node<T>* node = get_node(std::move(name));
        for (auto& x : nodes) {
            if (x == node)
                continue;
            erase_if(x.vc.begin(), x.vc.end(), [node](auto& x){return x.second == node;});
        }
        long long int index = node_to_index[node];
        node_to_index.erase(node);
        nodes.erase(index);
        for (auto& x : node_to_index) {
            if (x.second > index)
                --x.second;
        }
    }

    void del_e(Node<T>* first, Node<T>* second, bool is_oriented=true) {
        erase_if(first->vc.begin(), first->vc.end(), [second](auto& x){return x.second == second;});
        if (!is_oriented)
            erase_if(second->vc.begin(), second->vc.end(), [first](auto& x){return x.second == first;});
    }

    void edit_v(Node<T>* node, T mark) {
        node->mark = mark;
    }

    void edit_e(Node<T>* first, Node<T>* second, long long int weight, bool is_oriented) {
        replace(first->vc.begin(), first->vc.end(), [second](auto& x){return x.second == second;}, {weight, second});
        if (!is_oriented)
            replace(second->vc.begin(), second->vc.end(), [first](auto& x){return x.second == first;}, {weight, first});

    }

    void print() { // костыльно зато красиво :3
        if (nodes.empty()) {
            cout << "graph is empty!\n";
            return;
        }
        size_t mx_size = 0;
        for (auto& x : nodes)
            if (x->name.size() > mx_size)
                mx_size = x->name.size();
        cout << string(mx_size + 1, ' ');
        for (auto& x : nodes)
            cout << x->name << ' ';
        cout << '\n';
        for (auto& x : nodes) {
            cout << string(mx_size - x->name.size(), ' ') << x->name << ' ';
            unordered_map<Node<T>*, long long int> tmp_m(0);
            for (auto& y : x->vc) {
                if (tmp_m[y.second])
                    tmp_m[y.second] = min(tmp_m[y.second], y.first);
                else
                    tmp_m[y.second] = y.first;
            }
            for (auto& y : nodes) {
                string tmp_s = to_string(tmp_m[y]);
                long long int tmp_i = y->name.size() - tmp_s.size() + 1;
                cout << string(tmp_i / 2, ' ') << tmp_s << string(tmp_i / 2 + tmp_i % 2, ' ');
            }
            cout << '\n';
        }
    }

    Node<T>* get_node(string name) {
        for (auto& x : nodes)
            if (x->name == name)
                return x;
        return nullptr;
    }

    vector<Node<T>*> get_nodes() {
        return nodes;
    }

private:

    vector<Node<T>*> nodes;
    unordered_map<Node<T>*, size_t> node_to_index;

};

vector<vector<string> > get_cycles(Graph<int>& g) {
    vector<vector<string> > res;
    for (auto& x : g.get_nodes()) {
        if (!x->mark)
            continue;
        stack<Node<int>*> s;
        g.edit_v(x, 1);
        s.push(x);
        while(!s.empty()) {
            auto top = s.top();
            for (long long int index = g.first(top); index != -1; index = g.next(top, index)) {
                auto node = g.vertex(top, index);
                if (node->mark == 2)
                    continue;
                if (node->mark == 0) {
                    g.edit_v(node, 1);
                    s.push(top);
                    continue;
                }
                if (node->mark == 1) {

                }
            }
        }
    }
    return res;
}

int main() {
    Graph<pair<int, string>> g;
    int node_count, edge_count;
    while (true) {
        try {
            cout << "Введите кол-во вершин: ";
            cin >> node_count;
            break;
        }
        catch (exception& e) {
            cout << "Неверный ввод! ";
        }
    }
    unordered_set<string> nodes_contained;
    for (int i = 1; i <= node_count; ++i) {
        string t;
        cout << "Введите название " << i << " вершины: ";
        cin >> t;
        g.add_v(t, {0, ""});
        nodes_contained.insert(t);
    }
    while (true) {
        try {
            cout << "Введите кол-во ребер: ";
            cin >> edge_count;
            break;
        }
        catch (exception& e) {
            cout << "Неверный ввод! ";
        }
    }
    for (int i = 0; i < edge_count; ++i) {
        string s1, s2;
        while (true) {
            try {
                cout << "Введите название двух вершин через пробел, между которыми добавить ребро: ";
                cin >> s1 >> s2;
                if (!nodes_contained.contains(s1) || !nodes_contained.contains(s2))
                    throw exception();
                break;
            } catch(exception& e) {
                cout << "В графе нет таких вершин! ";
            }
        }
        g.add_e(g.get_node(s1), g.get_node(s2), 1);
    }
    g.print();
    return 0;
}