#include "bits/stdc++.h"
#include "boost/bimap.hpp"

using namespace std;

namespace lab2{
    class Graph{
    public:
        vector<bool> visited;
        Graph(int size) : visited(size, false){
            for(int i = 0; i < size; ++i){
                matrix.push_back(vector<int>(size,0));
                string s;
                cout << "Enter name v : ";
                cin >> s;
                ItN[i] = s;
                NtI[s] = i;
            }

        }
        auto First(string v){
            if(!matrix[NtI[v]].empty()){
                if(NtI[v] >= matrix.size())
                    throw runtime_error("going beyond the boundaries of the matrix");
                else{
                    for(int i = 0; i < matrix[NtI[v]].size(); ++i){
                        if(matrix[NtI[v]][i] != 0)
                            return i;
                    }
                    return -1;
                }
            } else
                throw runtime_error("height does not exist");
        }

        auto Next(string v, int i){
            if(!matrix[NtI[v]].empty()){
                if(i == matrix[NtI[v]].size() - 1){
                    return -1;
                }
                for(int x = i + 1; i < matrix[0].size(); ++i){
                    if(matrix[NtI[v]][x] != 0)
                        return x;
                }
                return -1;
            }
            else
                throw runtime_error("height does not exist");
        }

        auto Vertex(string v, int i){
            if(!matrix[NtI[v]].empty()){
                if(i == 0)
                    return First(v);
                int c = First(v);
                while(i != 0){
                    c = Next(v, c);
                    --i;
                }
                return c;
            }
                else throw runtime_error("height does not exist");

        }

        auto Add_V(string v){
            NtI[v] = matrix.size();
            ItN[matrix.size()] = v;
            matrix.push_back(vector<int>(matrix[0].size(), 0));
            for(auto& x : matrix){
                if(!x.empty())
                    x.push_back(0);
            }
        }

        auto Add_E(string v, string w, int c){
            matrix[NtI[v]][NtI[w]] = c;
        }

        auto Del_V(string v){
            matrix[NtI[v]].clear();
            for(int i = 0; i < matrix.size(); ++i){
                if(!matrix[i].empty()){
                    matrix[i][NtI[v]] = 0;
                }
            }
            ItN.erase(NtI[v]);
            NtI.erase(v);

        }

        auto Del_E(string v, string w){
            matrix[NtI[v]][NtI[w]] = 0;
        }

        auto Edit_V(string v, bool mark){
            visited[NtI[v]] = mark;
        }

        auto Edit_E(string v, string w, int c){
            matrix[NtI[v]][NtI[w]] = c;
        }

        auto print(){
            cout << endl;
            for(int i = 0; i < matrix.size(); ++i){
                if(!matrix[i].empty()) {
                    for (int j = 0; j < matrix[i].size(); ++j) {
                        if(ItN.contains(j))
                            cout << matrix[i][j] << ' ';
                    }
                    cout << endl;
                }

            }
        }

        int count(){
            return NtI.size();
        }

        void dfs(string name){
            if(visited[NtI[name]])
                return;
            visited[NtI[name]] = true;
            cout << name << ' ';
            int v = First(name);
            if(v == -1)
                return;
            else{
                dfs(ItN[v]);
                v = Next(name, v);
                while(v != -1){
                    dfs(ItN[v]);
                    v = Next(name, v);
                }
                return;
            }

        }

        auto GetWeight(int i, int j) { if(i < count() && j < count()) return matrix[i][j]; else throw runtime_error("l");}



        void dfs(string name, vector<string>& res, long long int k, string way = "") {
            if (visited[NtI[name]] || k < 0)
                return;
            way += ' ' + name;
            if (k == 0) {
                res.push_back(way);
                return;
            }
            Edit_V(name, true);
            for (long long index = First(name); index != -1; index = Next(name, index)) {
                auto v = Vertex(name, index);
                dfs(ItN[v], res, k - GetWeight(NtI[name], v), way);
            }
            Edit_V(name, false);
        }

        vector<string> get_ways( long long int k) {
            vector<string> res;
            for (auto& x : NtI) {
                string way = "";
                dfs(x.first, res, k, way);
                res.push_back(way);
            }
            return res;
        }


    private:
        vector<vector<int>> matrix;
        map<string, int> NtI;
        map<int, string> ItN;
    };
}

#ifndef ALGORITHMS_LAB2_H
#define ALGORITHMS_LAB2_H

#endif //ALGORITHMS_LAB2_H