#include <exception>
#include <iostream>
#include <string>

namespace global {
    // Throws std::runtime_error
    void logAndThrowException(const std::string &error);

    // Throws std::runtime_error if !cond
    void assertf(bool cond, const std::string &error);
} // namespace global

// TODO: parse intervals format like n=[10,100]

#include <exception>
#include <iostream>
#include <limits>
#include <map>
#include <optional>
#include <set>
#include <string>

/*
 * Simple argument parser. For exmple:
   "gen n=10 m=1e5 k=2.5e5 shuffle random"
    will be parsed as
    1. Parameters: {"n": "10", "m": "1e5", k: "2.5e5"}
    2. Flags: {"shuffle", "random"}
 * Throws and log an exception in case something went wrong.
 */

class ArgumentParser {
public:
    ArgumentParser();
    ArgumentParser(int argc, char *argv[]);

    bool hasFlag(const std::string &flagName) const;
    bool hasParameter(const std::string &parameterName) const;

    std::string getString(const std::string &parameterName,
                          std::optional<std::string> defaultValue = std::nullopt) const;
    int getInt(const std::string &parameterName,
               std::optional<int> defaultValue = std::nullopt) const;
    long long getLong(const std::string &parameterName,
                      std::optional<long long> defaultValue = std::nullopt) const;
    double getDouble(const std::string &parameterName,
                     std::optional<double> defaultValue = std::nullopt) const;

private:
    std::map<std::string, std::string> parameters_;
    std::set<std::string> flags_;
};

#include <utility>
#include <vector>

class UndirectedGraph {
public:
    UndirectedGraph(int size = 0);
    UndirectedGraph(int size, const std::vector<std::pair<int, int>> &edges);

    // (number of vertices, number of edges)
    std::pair<int, int> size() const;
    std::vector<std::pair<int, int>> edges() const;
    std::vector<std::vector<int>> graph() const;
    bool hasEdge(std::pair<int, int> edge) const;

    // Removes all edges, that became invalid
    void resize(int newSize);
    bool isTree() const;
    int components() const;
    std::vector<int> getDegreeSequence() const;

    // Merge edges of two graphs on the same vertices
    static UndirectedGraph mergeEdges(const UndirectedGraph &graph1, const UndirectedGraph &graph2,
                                      bool keepMultipleEdges);

private:
    int size_;
    std::vector<std::pair<int, int>> edges_;
};

/*
 * Generator of all size^(size * (size - 1) / 2) numbered undirected graphs.
 * How to use:

AllUndirectedGraphsGenerator generator(size);
do {
    auto graph = generator.buildGraph();
    ...
} while (graph.next());
*/

namespace random::graph::undirected {
    class AllUndirectedGraphsGenerator {
    public:
        AllUndirectedGraphsGenerator(int size);
        UndirectedGraph buildGraph() const;
        bool next();

        // Returns the number of already builded graphs
        int buildedGraphs() const;

    private:
        int size_;
        int edgesMask_{0};
        int buildedGraphs_{0};
    };
} // namespace random::graph::undirected

/*
 * Simple utils for generating random undirected graphs.
 * In case any error std::runtime_error will be throwed.
 */

namespace random::graph::undirected {
    // Generates random graph with no loops and multiple-edges.
    template<typename random_t>
    UndirectedGraph randomNoLoopsAndMultipleEdges(int vertices, int edges, random_t &rng);
} // namespace random::graph::undirected

#include <vector>

/*
 * Generator of all size^(size - 2) numbered trees.
 * How to use:

AllTreesGenerator generator(size);
do {
    auto graph = generator.buildGraph();
    ...
} while (graph.next());
*/

namespace random::tree {
    class AllTreesGenerator {
    public:
        AllTreesGenerator(int size);
        UndirectedGraph buildGraph() const;
        bool next();

        // Returns the number of already builded graphs
        int buildedGraphs() const;

    private:
        int size_;
        std::vector<int> prufer_;
        int buildedGraphs_{0};
    };
} // namespace random::tree

#include <vector>

namespace random::tree {
    // Generates completely random numbered tree.
    template<typename random_t>
    UndirectedGraph randomPruferCode(int vertices, random_t &rng);

    // Decodes Prufer code.
    UndirectedGraph decodePruferCode(const std::vector<int> &prufer);

    // Generates random forest with 'edges' edges by using randomPruferCode and removing random
    // extra edges.
    template<typename random_t>
    UndirectedGraph randomPruferForest(int vertices, int edges, random_t &rng);

    // Generates random bamboo with root 'root' (if -1 then root is random).
    template<typename random_t>
    UndirectedGraph bamboo(int vertices, int root, bool shuffle, random_t &rng);

    // Generates star with root at 'root' (if -1 then root is random).
    template<typename random_t>
    UndirectedGraph star(int vertices, int root, random_t &rng);

    // Returns parent array of size 'graph.size().first' where parent[0] = -1 and parent[i] < i
    // (parent of vertex i).
    std::vector<int> decodeParentArray(const UndirectedGraph &graph, int root = 0);
} // namespace random::tree

#include <algorithm>
#include <numeric>
#include <set>
#include <string>
#include <utility>
#include <vector>

/*
 * Simple utils for randomizing things.
 * random_t must have .next(n) method defined for every integral type
   which returns random number on the interval [0, n).
   Example: random_t from https://github.com/MikeMirzayanov/testlib/blob/master/testlib.h
 * In case any error std::runtime_error will be throwed.
 */

namespace random {
    // Random number on the interval [minValue, maxValue)
    template<typename T, typename random_t>
    T random(const T &minValue, const T &maxValue, random_t &rng);

    // Shuffles the range
    template<typename iterator_t, typename random_t>
    void shuffle(iterator_t beg, iterator_t end, random_t &rng);

    // Returns random element from non empty array options
    template<typename T, typename random_t>
    T choice(const std::vector<T> &options, random_t &rng);

    // Generates n distinct random integers from [minValue, maxValue)
    // Returned integers are not sorted
    template<typename T, typename random_t>
    std::vector<T> distinctIntegers(const T &minValue, const T &maxValue, int n, random_t &rng);

    // Generates random vector of size 'tests' with values >= 'minSize' and the sum equal to
    // 'totalSize'
    template<typename T, typename random_t>
    std::vector<T> distributeSize(T totalSize, const T &minSize, int tests, random_t &rng);

    // Generates random vector of size 'size' of elements from [minValue, maxValue)
    template<typename T, typename random_t>
    std::vector<T> array(int size, const T &minValue, const T &maxValue, random_t &rng);

    // Generates random vector of size 'size' of elements from [minValue, maxValue)
    // Contains all elements from [minValue, maxValue)
    template<typename T, typename random_t>
    std::vector<T> distributeToGroups(int size, const T &minValue, const T &maxValue,
                                      random_t &rng);
} // namespace random

#include <vector>

namespace random {
    /*
     * Insert an element.
     * Get a random element.
     * Extract a random element.
     */
    template<typename T>
    class Multiset {
    public:
        Multiset() = default;
        void insert(const T &value);

        template<typename random_t>
        T get(random_t &rng);

        template<typename random_t>
        T extract(random_t &rng);

    private:
        template<typename random_t>
        size_t randomIndex(random_t &rng);

        std::vector<T> data_;
    };
} // namespace random

namespace random {
    template<typename T>
    void Multiset<T>::insert(const T &value) {
        data_.push_back(value);
    }

    template<typename T>
    template<typename random_t>
    T Multiset<T>::get(random_t &rng) {
        return data_[randomIndex(rng)];
    }

    template<typename T>
    template<typename random_t>
    T Multiset<T>::extract(random_t &rng) {
        std::swap(data_[randomIndex(rng)], data_.back());
        auto value = data_.back();
        data_.pop_back();
        return value;
    }

    template<typename T>
    template<typename random_t>
    size_t Multiset<T>::randomIndex(random_t &rng) {
        global::assertf(!data_.empty(),
                        "[Multiset] trying to get a random element from an empty set");
        return random<size_t>(0, data_.size(), rng);
    }
} // namespace random

#include <algorithm>
#include <vector>

namespace random {
    /*
     * Add option with weight w_i (w_i >= 0).
     * Pop last option.
     * Options are enumerated from left to right (0-indexed).
     * Choose random option. Option i is choosed with probability w_i / sum w_i.
     ! Warning: sum of w_i should fit in T.
     */
    template<typename T>
    class Multichoice {
    public:
        Multichoice() = default;
        Multichoice(const std::vector<T> &w);

        void addOption(T w);
        void popOption();

        template<typename random_t>
        int choose(random_t &rng) const;

    private:
        std::vector<T> prefW = {0};
    };
} // namespace random

namespace random {
    template<typename T>
    Multichoice<T>::Multichoice(const std::vector<T> &w) {
        for (const auto &x : w) {
            addOption(x);
        }
    }

    template<typename T>
    void Multichoice<T>::addOption(T w) {
        global::assertf(w >= 0, "[Multichoice] w >= 0 not satisfied");
        prefW.push_back(prefW.back() + w);
    }

    template<typename T>
    void Multichoice<T>::popOption() {
        prefW.pop_back();
        global::assertf(!prefW.empty(),
                        "[Multichoice] popOption is called when there is no option");
    }

    template<typename T>
    template<typename random_t>
    int Multichoice<T>::choose(random_t &rng) const {
        global::assertf(prefW.back() > 0, "[Multichoice] no options to choose from");
        auto which = random::random(0, prefW.back(), rng);
        return std::upper_bound(prefW.begin(), prefW.end(), which) - prefW.begin() - 1;
    }
} // namespace random

namespace {
    template<typename T>
    std::optional<std::string> toOptionalString(const std::optional<T> &value) {
        std::optional<std::string> valueString;
        if (value.has_value()) {
            valueString = std::to_string(value.value());
        }
        return valueString;
    }

    // Checks whether string looks like 3e5
    std::optional<long long> tryGetDoubleToLong(std::string value) {
        bool negative = (!value.empty() && value[0] == '-');
        if (negative) {
            value = value.substr(1);
        }

        size_t splitPosition = value.find('e');
        if (splitPosition == std::string::npos || splitPosition == 0 ||
            splitPosition == value.size() - 1 || splitPosition > 19) {
            return std::nullopt;
        }

        size_t floatingPointPosition = value.find(".");
        if (floatingPointPosition != std::string::npos && floatingPointPosition > splitPosition) {
            return std::nullopt;
        }

        for (int i = 0; i < int(value.size()); i++) {
            if (i != int(splitPosition) && i != int(floatingPointPosition) &&
                !std::isdigit(value[i])) {
                return std::nullopt;
            }
        }

        long long result = 0;
        for (int i = 0; i < int(splitPosition); i++) {
            if (i != int(floatingPointPosition)) {
                result = result * 10 + (value[i] - '0');
            }
        }

        long long power = std::stoll(value.substr(splitPosition + 1));
        if (floatingPointPosition != std::string::npos) {
            power -= splitPosition - floatingPointPosition - 1;
        }
        if (power < 0) {
            return std::nullopt;
        }

        for (int i = 0; i < power; i++) {
            if (result > std::numeric_limits<long long>::max() / 10) {
                return std::nullopt;
            }
            result *= 10;
        }
        return negative ? -result : result;
    }
} // namespace

ArgumentParser::ArgumentParser() {}

ArgumentParser::ArgumentParser(int argc, char *argv[]) {
    for (int i = 1; i < argc; i++) {
        std::string preset = argv[i];
        size_t splitPosition = preset.find("=");
        if (splitPosition != std::string::npos) {
            parameters_[preset.substr(0, splitPosition)] = preset.substr(splitPosition + 1);
        } else {
            flags_.emplace(std::move(preset));
        }
    }
}

bool ArgumentParser::hasFlag(const std::string &flagName) const {
    return flags_.count(flagName) != 0;
}

bool ArgumentParser::hasParameter(const std::string &parameterName) const {
    return parameters_.count(parameterName) != 0;
}

std::string ArgumentParser::getString(const std::string &parameterName,
                                      std::optional<std::string> defaultValue) const {
    auto it = parameters_.find(parameterName);
    if (!defaultValue.has_value() && it == parameters_.end()) {
        global::logAndThrowException("Incorrect parameter: " + parameterName);
    }
    return it == parameters_.end() ? defaultValue.value() : it->second;
}

int ArgumentParser::getInt(const std::string &parameterName,
                           std::optional<int> defaultValue) const {
    std::string value = getString(parameterName, toOptionalString(defaultValue));
    if (auto result = tryGetDoubleToLong(value); result.has_value()) {
        if (std::numeric_limits<int>::min() <= result.value() &&
            result.value() <= std::numeric_limits<int>::max()) {
            return result.value();
        }
    }

    try {
        size_t auxPos{};
        int parsedInt = std::stoi(value, &auxPos);
        global::assertf(auxPos == value.size(), "Did not fully parsed int for parameter: " +
                                                    parameterName + ", value: " + value);
        return parsedInt;
    } catch (const std::invalid_argument &ex) {
        global::logAndThrowException("Did not parse int for parameter: " + parameterName +
                                     ", value: " + value);
    } catch (std::out_of_range const &ex) {
        global::logAndThrowException("Overflow happened while parsing int for parameter: " +
                                     parameterName + ", value: " + value);
    }
    return 0;
}

long long ArgumentParser::getLong(const std::string &parameterName,
                                  std::optional<long long> defaultValue) const {
    std::string value = getString(parameterName, toOptionalString(defaultValue));
    if (auto result = tryGetDoubleToLong(value); result.has_value()) {
        return result.value();
    }

    try {
        size_t auxPos{};
        long long parsedLong = std::stoll(value, &auxPos);
        global::assertf(auxPos == value.size(), "Did not fully parsed long long for parameter: " +
                                                    parameterName + ", value: " + value);
        return parsedLong;
    } catch (const std::invalid_argument &ex) {
        global::logAndThrowException("Did not parse long long for parameter: " + parameterName +
                                     ", value: " + value);
    } catch (std::out_of_range const &ex) {
        global::logAndThrowException("Overflow happened while parsing long long for parameter: " +
                                     parameterName + ", value: " + value);
    }
    return 0ll;
}

double ArgumentParser::getDouble(const std::string &parameterName,
                                 std::optional<double> defaultValue) const {
    std::string value = getString(parameterName, toOptionalString(defaultValue));
    try {
        size_t auxPos{};
        double parsedDouble = std::stod(value, &auxPos);
        global::assertf(auxPos == value.size(), "Did not fully parsed double for parameter: " +
                                                    parameterName + ", value: " + value);
        return parsedDouble;
    } catch (const std::invalid_argument &ex) {
        global::logAndThrowException("Did not parse double for parameter: " + parameterName +
                                     ", value: " + value);
    } catch (std::out_of_range const &ex) {
        global::logAndThrowException("Overflow happened while parsing double for parameter: " +
                                     parameterName + ", value: " + value);
    }
    return 0.;
}

#include <set>
#include <vector>

namespace random::graph::undirected {
    template<typename random_t>
    UndirectedGraph randomNoLoopsAndMultipleEdges(int vertices, int edges, random_t &rng) {
        global::assertf(vertices >= 0,
                        "[randomNoLoopsAndMultipleEdges] Negative number of vertices: " +
                            std::to_string(vertices));
        global::assertf(edges >= 0, "[randomNoLoopsAndMultipleEdges] Negative number of edges: " +
                                        std::to_string(edges));
        long long maxNumberOfEdges = 1ll * vertices * (vertices - 1) / 2;
        global::assertf(edges <= maxNumberOfEdges,
                        "[randomNoLoopsAndMultipleEdges] There is no graph with " +
                            std::to_string(vertices) + " vertices and " + std::to_string(edges) +
                            " edges.");

        if (edges * 2 > maxNumberOfEdges) {
            std::vector<std::pair<int, int>> options;
            options.reserve(maxNumberOfEdges);
            for (int v = 0; v < vertices; v++) {
                for (int u = v + 1; u < vertices; u++) {
                    options.emplace_back(v, u);
                }
            }
            random::shuffle(options.begin(), options.end(), rng);
            return UndirectedGraph(vertices, std::vector<std::pair<int, int>>(
                                                 options.begin(), options.begin() + edges));
        }

        std::set<std::pair<int, int>> edgesSet;
        for (int i = 0; i < edges; i++) {
            int v, u;
            do {
                v = random::random(0, vertices, rng);
                u = random::random(0, vertices, rng);
            } while (v == u || !edgesSet.insert(std::minmax(v, u)).second);
        }
        return UndirectedGraph(vertices,
                               std::vector<std::pair<int, int>>(edgesSet.begin(), edgesSet.end()));
    }
} // namespace random::graph::undirected

#include <algorithm>
#include <vector>

namespace random::tree {
    AllTreesGenerator::AllTreesGenerator(int size) : size_(size), prufer_(std::max(0, size_ - 2)) {}

    UndirectedGraph AllTreesGenerator::buildGraph() const {
        if (size_ <= 1) {
            return UndirectedGraph(size_);
        }
        if (size_ == 2) {
            return UndirectedGraph(size_, {{0, 1}});
        }
        return random::tree::decodePruferCode(prufer_);
    }

    bool AllTreesGenerator::next() {
        if (size_ <= 2) {
            return false;
        }
        int index = size_ - 3;
        while (index >= 0 && prufer_[index] == size_ - 1) {
            index--;
        }
        if (index < 0) {
            return false;
        }

        prufer_[index]++;
        std::fill(prufer_.begin() + index + 1, prufer_.end(), 0);
        buildedGraphs_++;
        return true;
    }

    int AllTreesGenerator::buildedGraphs() const {
        return buildedGraphs_;
    }
} // namespace random::tree

#include <algorithm>
#include <numeric>

UndirectedGraph::UndirectedGraph(int size) : size_(size) {}

UndirectedGraph::UndirectedGraph(int size, const std::vector<std::pair<int, int>> &edges)
    : size_(size), edges_(edges) {
    for (auto &[v, u] : edges_) {
        if (v > u) {
            std::swap(v, u);
        }
    }
    std::sort(edges_.begin(), edges_.end());
}

std::pair<int, int> UndirectedGraph::size() const {
    return {size_, edges_.size()};
}

std::vector<std::pair<int, int>> UndirectedGraph::edges() const {
    return edges_;
}

std::vector<std::vector<int>> UndirectedGraph::graph() const {
    std::vector<std::vector<int>> graph(size_);
    for (const auto &[v, u] : edges_) {
        graph[v].push_back(u);
        if (v != u) {
            graph[u].push_back(v);
        }
    }
    return graph;
}

bool UndirectedGraph::hasEdge(std::pair<int, int> edge) const {
    if (edge.first > edge.second) {
        std::swap(edge.first, edge.second);
    }
    return std::binary_search(edges_.begin(), edges_.end(), edge);
}

void UndirectedGraph::resize(int newSize) {
    if (newSize < size_) {
        auto newEnd =
            std::remove_if(edges_.begin(), edges_.end(), [this](const std::pair<int, int> &edge) {
                return edge.second >= size_;
            });
        edges_.erase(newEnd, edges_.end());
    }
    size_ = newSize;
}

bool UndirectedGraph::isTree() const {
    return int(edges_.size()) == size_ - 1 && components() == 1;
}

int UndirectedGraph::components() const {
    std::vector<int> parent(size_);
    std::iota(parent.begin(), parent.end(), 0);

    auto root = [&](auto self, int v) -> int {
        return parent[v] == v ? v : (parent[v] = self(self, parent[v]));
    };

    int components = size_;
    for (auto [v, u] : edges_) {
        v = root(root, v);
        u = root(root, u);
        if (v != u) {
            components--;
            parent[v] = u;
        }
    }
    return components;
}

std::vector<int> UndirectedGraph::getDegreeSequence() const {
    std::vector<int> degree(size_);
    for (const auto &[v, u] : edges_) {
        degree[v]++;
        degree[u]++;
    }
    return degree;
}

UndirectedGraph UndirectedGraph::mergeEdges(const UndirectedGraph &graph1,
                                            const UndirectedGraph &graph2, bool keepMultipleEdges) {
    global::assertf(
        graph1.size().first == graph2.size().first,
        "[UndirectedGraph.mergeEdges] Can not merge two graphs on a different number of vertices");
    auto edges1 = graph1.edges();
    auto edges2 = graph1.edges();
    std::vector<std::pair<int, int>> mergedEdges(edges1.size() + edges2.size());
    std::merge(edges1.begin(), edges1.end(), edges2.begin(), edges2.end(), mergedEdges.begin());

    if (!keepMultipleEdges) {
        mergedEdges.erase(std::unique(mergedEdges.begin(), mergedEdges.end()), mergedEdges.end());
    }
    return UndirectedGraph(graph1.size().first, mergedEdges);
}

#include <utility>
#include <vector>

namespace random::graph::undirected {
    AllUndirectedGraphsGenerator::AllUndirectedGraphsGenerator(int size) : size_(size) {}

    UndirectedGraph AllUndirectedGraphsGenerator::buildGraph() const {
        std::vector<std::pair<int, int>> edges;
        edges.reserve(__builtin_popcount(edgesMask_));

        std::pair<int, int> currentPair{0, 1};
        for (int mask = edgesMask_; mask != 0; mask >>= 1) {
            if (mask % 2 == 1) {
                edges.push_back(currentPair);
            }
            if (++currentPair.second == size_) {
                currentPair.first++;
                currentPair.second = currentPair.first + 1;
            }
        }
        return UndirectedGraph(size_, edges);
    }

    bool AllUndirectedGraphsGenerator::next() {
        int pairs = size_ * (size_ - 1) / 2;
        if (pairs <= 60 && edgesMask_ + 1 == (1ll << pairs)) {
            return false;
        }

        edgesMask_++;
        buildedGraphs_++;
        return true;
    }

    int AllUndirectedGraphsGenerator::buildedGraphs() const {
        return buildedGraphs_;
    }
} // namespace random::graph::undirected

#include <algorithm>
#include <functional>
#include <numeric>

namespace random::tree {
    template<typename random_t>
    UndirectedGraph randomPruferCode(int vertices, random_t &rng) {
        global::assertf(vertices >= 0, "[randomPruferCode] Negative number of vertices: " +
                                           std::to_string(vertices));
        if (vertices <= 1) {
            return UndirectedGraph(vertices);
        }
        if (vertices == 2) {
            return UndirectedGraph(vertices, {{0, 1}});
        }
        std::vector<int> prufer(vertices - 2);
        for (auto &vertex : prufer) {
            vertex = random::random(0, vertices, rng);
        }
        return decodePruferCode(prufer);
    }

    UndirectedGraph decodePruferCode(const std::vector<int> &prufer) {
        int vertices = prufer.size() + 2;
        std::vector<int> count(vertices);
        for (auto vertex : prufer) {
            count[vertex]++;
        }

        std::vector<std::pair<int, int>> edges;
        edges.reserve(vertices - 1);
        int pointer = 0;
        int option = -1;

        for (auto vertex : prufer) {
            if (option == -1) {
                while (count[pointer] > 0) {
                    pointer++;
                }
                option = pointer++;
            }
            edges.emplace_back(vertex, option);
            option = -1;
            if (--count[vertex] == 0 && vertex < pointer) {
                option = vertex;
            }
        }

        if (vertices == 2 || prufer.back() == vertices - 1) {
            while (count[pointer] > 0) {
                pointer++;
            }
            edges.emplace_back(pointer, vertices - 1);
        } else {
            edges.emplace_back(prufer.back(), vertices - 1);
        }
        return UndirectedGraph(vertices, edges);
    }

    template<typename random_t>
    UndirectedGraph randomPruferForest(int vertices, int edges, random_t &rng) {
        global::assertf(0 <= edges && edges < vertices,
                        "[randomPruferForest] 0 <= edges < vertices must holds.");
        auto tree = randomPruferCode(vertices, rng).getEdges();
        random::shuffle(tree.begin(), tree.end(), rng);
        tree.resize(edges);
        return UndirectedGraph(vertices, tree);
    }

    template<typename random_t>
    UndirectedGraph bamboo(int vertices, int root, bool shuffle, random_t &rng) {
        global::assertf(-1 <= root && root < vertices,
                        "[bamboo] root must be from interval [-1, n).");
        if (vertices == 0) {
            return UndirectedGraph();
        }

        if (root == -1) {
            root = random::random(0, vertices, rng);
        }

        std::vector<int> order(vertices);
        std::iota(order.begin(), order.end(), 0);
        std::swap(order[root], order[0]);

        if (shuffle) {
            random::shuffle(order.begin() + 1, order.end(), rng);
        }

        std::vector<std::pair<int, int>> edges(vertices - 1);
        for (int i = 0; i + 1 < vertices; i++) {
            edges[i] = std::make_pair(order[i], order[i + 1]);
        }
        return UndirectedGraph(vertices, edges);
    }

    template<typename random_t>
    UndirectedGraph star(int vertices, int root, random_t &rng) {
        global::assertf(-1 <= root && root < vertices,
                        "[star] root must be from interval [-1, n).");
        if (vertices == 0) {
            return UndirectedGraph();
        }

        if (root == -1) {
            root = random::random(0, vertices, rng);
        }
        std::vector<std::pair<int, int>> edges;
        edges.reserve(vertices - 1);
        for (int i = 0; i < vertices; i++) {
            if (i != root) {
                edges.emplace_back(i, root);
            }
        }
        return UndirectedGraph(vertices, edges);
    }

    std::vector<int> decodeParentArray(const UndirectedGraph &graph, int root) {
        global::assertf(graph.isTree(),
                        "[decodeParentArray] Can't decode parents for non-tree graph.");

        const auto g = graph.graph();
        std::vector<int> parents(graph.size().first, -1);
        int free_index = 0;

        std::function<void(int, int)> dfs = [&](int v, int p) -> void {
            int index = free_index;
            free_index++;
            for (auto u : g[v]) {
                if (u != p) {
                    parents[free_index] = index;
                    dfs(u, v);
                }
            }
        };

        dfs(root, root);
        return parents;
    }
} // namespace random::tree

namespace random {
    template<typename T, typename random_t>
    T random(const T &minValue, const T &maxValue, random_t &rng) {
        global::assertf(minValue < maxValue,
                        "[random] Can not create random number on the interval [" +
                            std::to_string(minValue) + ", " + std::to_string(maxValue) + ")");
        return minValue + rng.next(maxValue - minValue);
    }

    template<typename iterator_t, typename random_t>
    void shuffle(iterator_t beg, iterator_t end, random_t &rng) {
        for (int i = 0; beg + i != end; i++) {
            int j = random(0, i + 1, rng);
            if (j != i) {
                std::swap(*(beg + i), *(beg + j));
            }
        }
    }

    template<typename T, typename random_t>
    T choice(const std::vector<T> &options, random_t &rng) {
        global::assertf(!options.empty(), "[choice]: options must be non empty");
        return options[random(0, (int)options.size(), rng)];
    }

    template<typename T, typename random_t>
    std::vector<T> distinctIntegers(const T &minValue, const T &maxValue, int n, random_t &rng) {
        global::assertf(maxValue - minValue >= n,
                        "[distinctIntegers] maxValue - minValue >= n must holds.");
        std::vector<T> result(n);
        if (maxValue - minValue <= 2 * n) {
            std::vector<T> elements(maxValue - minValue);
            std::iota(elements.begin(), elements.end(), minValue);
            random::shuffle(elements.begin(), elements.end(), rng);
            for (int i = 0; i < n; i++) {
                result[i] = elements[i];
            }
        } else {
            std::set<T> got;
            for (auto &value : result) {
                do {
                    value = random(minValue, maxValue, rng);
                } while (!got.insert(value).second);
            }
        }
        return result;
    }

    template<typename T, typename random_t>
    std::vector<T> distributeSize(T totalSize, const T &minSize, int tests, random_t &rng) {
        global::assertf(tests >= 1, "[distributeSize] 'tests' must be at least one.");
        global::assertf(1ll * minSize * tests <= totalSize,
                        "[distributeSize] totalSize is less than minSize * tests.");

        totalSize -= minSize * tests;
        auto borders = distinctIntegers<T>(0, totalSize + tests - 1, tests - 1, rng);
        std::sort(borders.begin(), borders.end());

        std::vector<T> result(tests);
        T lastBorder = -1;
        for (int i = 0; i + 1 < tests; i++) {
            result[i] = borders[i] - lastBorder - 1 + minSize;
            lastBorder = borders[i];
        }
        result.back() =
            totalSize + minSize * tests - std::accumulate(result.begin(), result.end(), T(0));
        return result;
    }

    template<typename T, typename random_t>
    std::vector<T> array(int size, const T &minValue, const T &maxValue, random_t &rng) {
        std::vector<T> result(size);
        for (auto &value : result) {
            value = random::random(minValue, maxValue, rng);
        }
        return result;
    }

    template<typename T, typename random_t>
    std::vector<T> distributeToGroups(int size, const T &minValue, const T &maxValue,
                                      random_t &rng) {
        global::assertf(maxValue - minValue <= size,
                        "[generateRandomGroups] maxValue - minValue <= size must holds");
        auto result = array(size, minValue, maxValue, rng);
        auto leaders = distinctIntegers(0, size, maxValue - minValue, rng);
        for (int i = 0; i < int(leaders.size()); i++) {
            result[leaders[i]] = minValue + i;
        }
        return result;
    }
} // namespace random

namespace global {
    void logAndThrowException(const std::string &error) {
        std::cerr << error << std::endl;
        throw std::runtime_error(error);
    }

    void assertf(bool cond, const std::string &error) {
        if (!cond) {
            logAndThrowException(error);
        }
    }
} // namespace global
