//din pacate, realizarea tuturor cerintelor intr-o singura clasa a dus la asta
//not my proudest work
//am pastrat cate un main pentru fiecare cerinta


#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <valarray>

class Node {
public:
    int id;
    std::vector<int> neighbors;
    int value;
    explicit Node(int id, int value = -1) : id(id), value(value) {}

    void setValue(int color_) {
        this->value = color_;
    }
    
    [[nodiscard]] int getValue() const {
        return this->value;
    }

    [[nodiscard]] int getId() const {
        return this->id;
    }
};

class Edge {
public:
    int src, dest;
    Edge(int src, int dest) : src(src), dest(dest) {}
};

class Graph {
private:
    std::vector<Node> nodes;
    std::vector<Edge> edges;

public:

    void printGraph() {
        for (int i = 0; i < nodes.size(); i++) {
            std::cout << nodes[i].id << '(' << nodes[i].value << ')' << ": ";
            for (int j = 0; j < nodes[i].neighbors.size(); j++) {
                std::cout << nodes[i].neighbors[j] << " ";
            }
            std::cout << std::endl;
        }
    }

    Graph() = default;

    explicit Graph(int n) {
        for (int i = 0; i < n; ++i) {
            nodes.emplace_back(i);
        }
    }

    void addAdjacentEdgesFormGridStructure(std::vector<std::vector<int>> &grid) {
        int n = int(grid.size());
        int m = int(grid[0].size());
        int node_id = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                nodes.emplace_back(node_id++);
            }
        }

        //add edges for corners
        if (checkEdge(0, 1) == 0)
            addEdge(0, 1);
        if (checkEdge(0, n) == 0)
            addEdge(0, n);
        if (checkEdge(n - 1, n - 2) == 0)
            addEdge(n - 1, n - 2);
        if (checkEdge(n - 1, 2 * n - 1) == 0)
            addEdge(n - 1, 2 * n - 1);
        if (checkEdge(int(nodes.size()) - n, int(nodes.size()) - n + 1) == 0)
            addEdge(int(nodes.size()) - n, int(nodes.size()) - n + 1);
        if (checkEdge(int(nodes.size()) - n, int(nodes.size()) - 2 * n) == 0)
            addEdge(int(nodes.size()) - n, int(nodes.size()) - 2 * n);
        if (checkEdge(int(nodes.size()) - 1, int(nodes.size()) - 2) == 0)
            addEdge(int(nodes.size()) - 1, int(nodes.size()) - 2);
        if (checkEdge(int(nodes.size()) - 1, int(nodes.size()) - n - 1) == 0)
            addEdge(int(nodes.size()) - 1, int(nodes.size()) - n - 1);

        //add edges for borders

//top border
        for (int i = 1; i < n - 1; ++i) {
            if (checkEdge(i, i - 1) == 0)
                addEdge(i, i - 1);
            if (checkEdge(i, i + 1) == 0)
                addEdge(i, i + 1);
            if (checkEdge(i, i + n) == 0)
                addEdge(i, i + n);
        }

//bottom border
        for (int i = int(nodes.size()) - n + 1; i < int(nodes.size()) - 1; ++i) {
            if (checkEdge(i, i - 1) == 0)
                addEdge(i, i - 1);
            if (checkEdge(i, i + 1) == 0)
                addEdge(i, i + 1);
            if (checkEdge(i, i - n) == 0)
                addEdge(i, i - n);
        }

//left border
        for (int i = n; i < int(nodes.size()) - n; i += n) {
            if (checkEdge(i, i - n) == 0)
                addEdge(i, i - n);
            if (checkEdge(i, i + n) == 0)
                addEdge(i, i + n);
            if (checkEdge(i, i + 1) == 0)
                addEdge(i, i + 1);
        }

//right border
        for (int i = 2 * n - 1; i < nodes.size() - n; i += n) {
            if (checkEdge(i, i - n) == 0)
                addEdge(i, i - n);
            if (checkEdge(i, i + n) == 0)
                addEdge(i, i + n);
            if (checkEdge(i, i - 1) == 0)
                addEdge(i, i - 1);
        }

        //add edges for the rest of the nodes

        for (int i = 0; i < nodes.size(); ++i) {
            if (i % n != 0 && i % n != n - 1 && i >= n && i < nodes.size() - n) {
                if (checkEdge(i, i - 1) == 0)
                    addEdge(i, i - 1);
                if (checkEdge(i, i + 1) == 0)
                    addEdge(i, i + 1);
                if (checkEdge(i, i - n) == 0)
                    addEdge(i, i - n);
                if (checkEdge(i, i + n) == 0)
                    addEdge(i, i + n);
            }
        }
    }

    explicit Graph(std::vector<std::vector<int>> &grid) {
        //add adjacent edges for the nodes
        addAdjacentEdgesFormGridStructure(grid);

        int n = int(std::sqrt(nodes.size()));

        //value the nodes that are marked as 1 in the grid
        for (int i = 0; i < nodes.size(); ++i) {
            if (grid[i / n][i % n] == 1) {
                nodes[i].setValue(1);
            }
        }
    }

    Graph(int n, const std::vector<std::vector<int>> &edges) {
        for (int i = 0; i <= n; i++) {
            addNode(i);
        }

        for (std::vector<int> edge: edges) {
            addEdge(edge[0], edge[1]);
        }
    }

    Graph(int n, int m, const std::vector<std::vector<int>> &edges) {
        for (int i = 0; i <= n; i++) {
            addNode(i);
        }

        for (std::vector<int> edge: edges) {
            addEdge(edge[0], edge[1]);
            addOrienteEdge(edge[1], edge[1]);
            addOrienteEdge(edge[0], edge[0]);
        }
    }

    void addNode(int id) {
        nodes.emplace_back(id);
    }

    void addEdge(int src, int dest) {
        edges.emplace_back(src, dest);
        nodes[src].neighbors.push_back(dest);
        nodes[dest].neighbors.push_back(src);
    }

    void addOrienteEdge(int src, int dest) {
        edges.emplace_back(src, dest);
        nodes[src].neighbors.push_back(dest);
    }

    bool checkEdge(int src, int dest) {
        for (int neighbor: nodes[src].neighbors) {
            if (neighbor == dest) {
                return true;
            }
        }
        return false;
    }

    int MakeGrafFromGridForest(std::vector<std::vector<int>> &grid, int pl, int pc, int cl, int cc) {
        pl--;
        pc--;
        cl--;
        cc--;

        struct Point {
            int x, y;

            Point(int x, int y) : x(x), y(y) {}
        };

        int m = int(grid.size());
        int n = int(grid[0].size());
        std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
        std::unordered_map<int, std::vector<int>> graph_this_;
        int clusterId = 0;

        // Definirea directiilor posibile pe grid
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};

        // Parcurgerea grid-ului
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!visited[i][j]) {
                    int cluster = grid[i][j];
                    std::queue<Point> q;
                    q.emplace(i, j);
                    std::vector<int> nodes_;

                    // Parcurgere BFS a cluster-ului
                    while (!q.empty()) {
                        Point p = q.front();
                        q.pop();
                        if (visited[p.x][p.y]) {
                            continue;
                        }
                        visited[p.x][p.y] = true;
                        nodes_.push_back(p.x * n + p.y); // Identificare nod
                        for (int k = 0; k < 4; ++k) {
                            int nx = p.x + dx[k];
                            int ny = p.y + dy[k];
                            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == cluster && !visited[nx][ny]) {
                                q.emplace(nx, ny);
                            }
                        }
                    }
                    graph_this_[clusterId] = nodes_; // Adaugare noduri in graf
                    clusterId++;
                }
            }
        }
        //adaugare noduri in graf
        for (int i = 0; i < clusterId; ++i) {
            addNode(i);
        }

        //adaugare muchii in graf
        //vom avea muchie intre 2 clusteruri daca acestea contin noduri daca acestea sunt vecini in grid
        for (int i = 0; i < clusterId; ++i) {
            for (int j = i + 1; j < clusterId; ++j) {
                for (int node1: graph_this_[i]) {
                    for (int node2: graph_this_[j]) {
                        if (node1 == node2 - 1 || node1 == node2 + 1 || node1 == node2 - n || node1 == node2 + n) {
                            addEdge(i, j);
                            break;
                        }
                    }
                }
            }
        }

        //eliminam duplicatele din listele de adiacenta ale nodurilor
        for (int i = 0; i < nodes.size(); ++i) {
            std::sort(nodes[i].neighbors.begin(), nodes[i].neighbors.end());
            nodes[i].neighbors.erase(std::unique(nodes[i].neighbors.begin(), nodes[i].neighbors.end()),
                                     nodes[i].neighbors.end());
        }

        //find cluster that contains the player
        int playerCluster = -1;
        for (int i = 0; i < clusterId; ++i) {
            for (int node: graph_this_[i]) {
                if (node == pl * n + pc) {
                    playerCluster = i;
                    break;
                }
            }
        }

        //find cluster that contains the chest
        int chestCluster = -1;
        for (int i = 0; i < clusterId; ++i) {
            for (int node: graph_this_[i]) {
                if (node == cl * n + cc) {
                    chestCluster = i;
                    break;
                }
            }
        }

        //find shortest path between the 2 clusters using BFS
        std::vector<int> colors(nodes.size(), -1);
        std::queue<int> q;
        std::vector<int> path;

        colors[playerCluster] = 0;
        q.push(playerCluster);

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            if (node == chestCluster) {
                break;
            }
            for (int neighbor: nodes[node].neighbors) {
                if (colors[neighbor] == -1) {
                    colors[neighbor] = node;
                    q.push(neighbor);
                }
            }
        }

        int answer = -1;
        int node_ = chestCluster;
        while (node_ != playerCluster) {
            path.push_back(node_);
            node_ = colors[node_];
        }
        path.push_back(playerCluster);
        std::reverse(path.begin(), path.end());
        for (int node: path) {
            answer++;
        }
        return answer;

    }

    bool isBipartite() {
        std::vector<int> colors(nodes.size(), -1);
        std::queue<int> q;

        for (int i = 1; i < nodes.size(); i++) {
            if (colors[i] == -1) {
                colors[i] = 0;
                q.push(i);

                while (!q.empty()) {
                    int node = q.front();
                    q.pop();

                    for (int neighbor: nodes[node].neighbors) {
                        if (colors[neighbor] == -1) {
                            colors[neighbor] = 1 - colors[node];
                            q.push(neighbor);
                        } else if (colors[neighbor] == colors[node]) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }

    bool topologicalSort(std::vector<int> &order) {
        std::vector<int> inDegree(nodes.size(), 0);

        for (const Edge &edge: edges) {
            inDegree[edge.dest]++;
        }

        std::queue<int> q;
        for (int i = 0; i < nodes.size(); ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int current = q.front();
            q.pop();
            order.push_back(current);

            for (int neighbor: nodes[current].neighbors) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return order.size() == nodes.size();
    }

    static std::vector<int> findOrder(int numCourses, std::vector<std::vector<int>> &prerequisites) {
        Graph graph;
        for (int i = 0; i < numCourses; ++i) {
            graph.addNode(i);
        }

        for (const auto &prerequisite: prerequisites) {
            graph.addEdge(prerequisite[1], prerequisite[0]);
        }

        std::vector<int> order;
        if (!graph.topologicalSort(order)) {
            return {};
        }

        return order;
    }

    void dfs(int node, int parent, int &time, std::vector<int> &low, std::vector<int> &discovery,
             std::vector<std::vector<int>> &bridges) {
        discovery[node] = low[node] = time++;

        for (int neighbor: nodes[node].neighbors) {
            if (neighbor == parent) {
                continue;
            }

            if (discovery[neighbor] == -1) {
                dfs(neighbor, node, time, low, discovery, bridges);
                low[node] = std::min(low[node], low[neighbor]);

                if (low[neighbor] > discovery[node]) {
                    bridges.push_back({node, neighbor});
                }
            } else {
                low[node] = std::min(low[node], discovery[neighbor]);
            }
        }
    }

    bool dfs(int node, std::vector<int> &visited, std::unordered_set<int> &unsafe, std::unordered_set<int> &safe) {
        if (unsafe.find(node) != unsafe.end()) {
            return false;
        }
        if (safe.find(node) != safe.end()) {
            return true;
        }

        visited[node] = 1;

        for (int neighbor: nodes[node].neighbors) {
            if (visited[neighbor] == 1 || !dfs(neighbor, visited, unsafe, safe)) {
                unsafe.insert(node);
                return false;
            }
        }

        visited[node] = 0;
        safe.insert(node);
        return true;
    }

    void dfs(int node, std::vector<int> &colors, int value) {
        colors[node] = value;
        for (int neighbor: nodes[node].neighbors) {
            if (colors[neighbor] == 1) {
                dfs(neighbor, colors, value);
            }
        }
    }

    void dfs(int v, int p, std::vector<int> &d) {
        if (p != -1) d[v] = d[p] + 1;
        for (int u: nodes[v].neighbors) {
            if (u != p) {
                dfs(u, v, d);
            }
        }
    }

    static std::vector<int> findSafeNodes(std::vector<std::vector<int>> &graph) {
        Graph directedGraph;
        for (int i = 0; i < graph.size(); ++i) {
            directedGraph.addNode(i);
            for (int neighbor: graph[i]) {
                directedGraph.addOrienteEdge(i, neighbor);
            }
        }

        std::vector<int> visited(graph.size(), -1);
        std::unordered_set<int> unsafe;
        std::unordered_set<int> safe;

        for (int i = 0; i < graph.size(); ++i) {
            if (visited[i] == -1) {
                directedGraph.dfs(i, visited, unsafe, safe);
            }
        }

        std::vector<int> result;
        for (int i = 0; i < graph.size(); ++i) {
            if (safe.find(i) != safe.end()) {
                result.push_back(i);
            }
        }
        return result;
    }

    int minFlipsToConnectTwoIslands() {
        std::vector<int> colors(nodes.size(), -1);

        for (int i = 0; i < nodes.size(); ++i) {
            colors[i] = nodes[i].value;
        }

        std::queue<int> q;

        // Find the first island
        for (int i = 0; i < nodes.size(); ++i) {
            if (colors[i] == 1 && !nodes[i].neighbors.empty()) {
                dfs(i, colors, 0);
                break;
            }
        }

        std::cout << std::endl;

        std::unordered_set<int> visited;
        while (!q.empty()) {
            int currentSize = int(q.size());
            for (int i = 0; i < currentSize; ++i) {
                int current = q.front();
                q.pop();
                visited.insert(current);
                for (int neighbor: nodes[current].neighbors) {
                    if (visited.find(neighbor) == visited.end()) {
                        if (colors[neighbor] == 1) {
                            return -1;
                        }
                        q.push(neighbor);
                    }
                }
            }
        }

        //add edges between all the adjacent nodes with different colors. Adjacent nodes for node I are nodes that,
        //in the original matrix, are in the same row or column of i. Node I is on row i/n and column i%n

        //calculate position of neighbors in the original matrix and add edges

        //find the shortest path between a nod that has value 0 and a node that has value 1

        std::vector<int> distances(nodes.size(), -1);
        std::queue<int> q1;
        for (int i = 0; i < nodes.size(); ++i) {
            if (colors[i] == 0) {
                q1.push(i);
                distances[i] = 0;
            }
        }
        //get the shortest path
        while (!q1.empty()) {
            int current = q1.front();
            q1.pop();
            for (int neighbor: nodes[current].neighbors) {
                if (distances[neighbor] == -1) {
                    distances[neighbor] = distances[current] + 1;
                    q1.push(neighbor);
                }
            }
        }

        int minDistance = INT_MAX;
        for (int i = 0; i < nodes.size(); ++i) {
            if (colors[i] == 1) {
                minDistance = std::min(minDistance, distances[i]);
            }
        }
        return minDistance - 1;
    }

    bool equationsPossible(std::vector<std::string> &equations) {
        Graph graph;
        for (int i = 0; i < 26; ++i) {
            graph.addNode(i);
        }
        for (const auto &equation: equations) {
            if (equation[1] == '=') {
                int src = equation[0] - 'a';
                int dest = equation[3] - 'a';
                if (!graph.checkEdge(src, dest)) {
                    graph.addEdge(src, dest);
                    graph.addEdge(dest, src);
                }
            }
        }

        std::vector<int> colors(26, -1);
        for (int i = 0; i < 26; ++i) {
            if (colors[i] == -1) {
                if (!equationsPossibleHelper(i, i, colors, graph)) {
                    return false;
                }
            }
        }

        for (const auto &equation: equations) {
            if (equation[1] == '!') {
                int src = equation[0] - 'a';
                int dest = equation[3] - 'a';
                if (src == dest || colors[src] == colors[dest]) {
                    return false;
                }
            }
        }
        return true;
    }

    bool equationsPossibleHelper(int node, int value, std::vector<int> &colors, Graph &graph) {
        if (colors[node] != -1) {
            return colors[node] == value;
        }

        colors[node] = value;
        for (int neighbor: graph.nodes[node].neighbors) {
            if (!equationsPossibleHelper(neighbor, value, colors, graph)) {
                return false;
            }
        }
        return true;
    }

    std::vector<std::vector<int>> findCriticalConnections(int n, std::vector<std::vector<int>> &connections) {
        Graph graph(n, connections);
        std::vector<int> low(n, -1), discovery(n, -1);
        std::vector<std::vector<int>> bridges;
        int time = 0;

        for (int i = 0; i < n; ++i) {
            if (discovery[i] == -1) {
                dfs(i, -1, time, low, discovery, bridges);
            }
        }

        return bridges;
    }

    bool directEdges() {
        std::vector<int> colors(nodes.size(), -1);
        for (int i = 0; i < nodes.size(); ++i) {
            if (colors[i] == -1) {
                if (!directEdgesHelper(i, colors)) {
                    return false;
                }
            }
        }
        return true;
    }

    bool directEdgesHelper(int node, std::vector<int> &colors) {
        if (colors[node] != -1) {
            return colors[node] == 1;
        }

        colors[node] = 1;
        for (int neighbor: nodes[node].neighbors) {
            if (!directEdgesHelper(neighbor, colors)) {
                return false;
            }
        }
        return true;
    }

    void orientEdges() {
        //consideram radacina ca fiind nodul 0
        if (!directEdges()) {
            std::cout << "NO";
        } else {
            std::cout << "YES\n";
            //orient edges: Start from first and orient from small to big
            for (auto edge: edges) {
                if (edge.src < edge.dest) {
                    std::cout << 0;
                } else {
                    std::cout << 1;
                }
            }
        }
    }

    int escapeTime(int n, int m, int k, std::vector<std::pair<int, std::vector<int>>> patrols) {

        std::vector<std::vector<int>> positions(k, std::vector<int>());
        std::vector<std::vector<int>> dp(n, std::vector<int>(420, INT_MAX));


        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < patrols[i].first; ++j) {
                positions[i].push_back(patrols[i].second[j]);
            }

        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 420; ++j) {
                dp[i][j] = INT_MAX;
            }
        }

        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < positions[i].size(); ++j) {
                for (int z = j; z < 420; z += positions[i].size()) {
                    dp[positions[i][j]][z] = -1;
                }
            }
        }

        std::queue<std::pair<int, int>> coada;
        coada.push(std::make_pair(0, 0));
        dp[0][0] = 0;
        while (!coada.empty()) {
            int elem = coada.front().first;
            int minutes = coada.front().second;
            coada.pop();

            for (int y: nodes[elem].neighbors) {
                if (dp[y][(minutes + 1) % 420] != -1 && dp[elem][minutes] + 1 < dp[y][(minutes + 1) % 420]) {
                    dp[y][(minutes + 1) % 420] = dp[elem][minutes] + 1;
                    coada.push(std::make_pair(y, (minutes + 1) % 420));
                }
            }
        }
        int minimum = INT_MAX;
        for (int i = 0; i < 420; ++i) {
            if (dp[n - 1][i] != -1) {
                minimum = minimum < dp[n - 1][i] ? minimum : dp[n - 1][i];

            }
        }
        if (minimum == INT_MAX) {
            return -1;
        } else {
            return minimum;
        }
    }

    static int MinimumMaximumDistance(){
        int n;

        int k;
        std::cin>>n>>k;
        Graph graph(n);

        std::vector<int> marked(k);

        for(auto &elem: marked){
            std::cin >> elem;
            --elem;
        }

        for(int i=1;i<n;i++){
            int u, v;
            std::cin >> u >> v;
            --u, --v;
            graph.addEdge(u, v);
        }

        if(k==1){
            return 0;
        }

        std::vector<int> d1(n);

        graph.dfs(marked[0], -1, d1);

        int mx = marked[0];

        for(int e: marked){
            if(d1[e] > d1[mx]) mx = e;
        }

        std::vector<int> d2(n);
        graph.dfs(mx, -1, d2);
        mx = marked[0];

        for(int e: marked){
            if(d2[e] > d2[mx]) mx = e;
        }

        return (d2[mx] + 1) / 2;

    }

    static void MinimumMaximumDistance(int t) {
        while (t--) {
            std::cout << MinimumMaximumDistance() << "\n";
        }
    }
};

// //main 1
//int main() {
//
//    int n = 4;
//    std::vector<std::vector<int>> dislikes = {{1, 2},
//                                              {1, 3},
//                                              {2, 4}};
//
//    Graph graph(n, dislikes);
//    std::cout << graph.isBipartite();
//
//}

// //main 2
//int main() {
//    Input: numCourses = 2, prerequisites = [[1,0]]
//        Output: [0,1]
//
//    int n = 2;
//    std::vector<std::vector<int>> prerequisites = {{1, 0}};
//
//    Graph graph(n, prerequisites);
//    std::vector<int> ceva = graph.findOrder(n, prerequisites);
//    for (auto elem: ceva) {
//        std::cout << elem << " ";
//    }
//    return 0;
//}

// //main 3
//int main() {
//
//    int n = 4;
//    std::vector<std::vector<int>> connections = {{0, 1},
//                                                 {1, 2},
//                                                 {2, 0},
//                                                 {1, 3}};
//
//    Graph graph(n, connections);
//    std::vector<std::vector<int>> ceva = graph.findCriticalConnections(n, connections);
//    for (auto elem: ceva) {
//        std::cout << elem[0] << " " << elem[1] << "\n";
//    }
//}

// //main 4
//int main(){
//    //find safe states
//    std::vector<std::vector<int>> graph = {{1,2},{2,3},{5},{0},{5},{},{}};
//    Graph graph1;
//    auto ceva = graph1.findSafeNodes(graph);
//    for (auto elem: ceva) {
//        std::cout << elem << " ";
//    }
//    return 0;
//}

// //main 5
//int main(){
//    //Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
//    //Output: 1
//
//    std::vector<std::vector<int>> grid = {{1,1,1,1,1},{1,0,0,0,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}};
//    Graph graph(grid);
//    return graph.minFlipsToConnectTwoIslands();
//}

// //main 6
//int main(){
//    //Input: equations = ["a==b","b!=a"]
//    //Output: false
//
//    std::vector<std::string> equations = {"a==b","b!=a"};
//
//    Graph graph;
//    return graph.equationsPossible(equations);
//}

// //main 7
//int main(){
//    //makeGraphFromForest
//    int n = 6;
//    int m = 5;
//    //pl pc cl cc
//    int pl = 1, pc = 1, cl = 5, cc = 4;
//    //0 0 0 5 6
//    //7 7 1 1 1
//    //1 1 1 3 1
//    //1 1 2 2 1
//    //0 0 9 0 0
//    //0 0 0 0 9
//    std::vector<std::vector<int>> forest = {{0, 0, 0, 5, 6},
//                                            {7, 7, 1, 1, 1},
//                                            {1, 1, 1, 3, 1},
//                                            {1, 1, 2, 2, 1},
//                                            {0, 0, 9, 0, 0},
//                                            {0, 0, 0, 0, 9}};
//    Graph g;
//    std::cout << g.MakeGrafFromGridForest(forest,  1, 1, 5, 4);
//}

// //main 8
//int main(){
//    //input
//    //6 5
//    //1 5
//    //2 1
//    //1 4
//    //3 1
//    //6 1
//
//    int n = 6;
//    std::vector<std::vector<int>> edges = {  {1, 5},
//                                             {2, 1},
//                                             {1, 4},
//                                             {3, 1},
//                                             {6, 1}};
//
//    Graph graph(n, edges);
//
//    std::cout;
//    graph.orientEdges();
//    return 0;
//}


// //main 9
//int main() {
//
//    int n, m, k;
//    n = 5;
//    m = 4;
//    k = 3;
//    std::vector<std::vector<int>> tunnels = {{0, 1},
//                                                {1, 2},
//                                                {2, 3},
//                                                {3, 4}};
//
//    std::vector<std::pair<int, std::vector<int>>> patrols = {{3, {4, 2, 3}},
//                                                             {2, {2, 1}},
//                                                             {2, {4, 3}}};
//
//    Graph graph(n, m, tunnels);
//
//    std::cout << graph.escapeTime(n, m, k, patrols);
//
//    return 0;
//}


 //main 10
//int main(){
//    int t;
//    std::cin>>t;
//    Graph::MinimumMaximumDistance(t);
//}