// When the degree sequence is not graphics, the Graph can be

    // in any state, it is not neccesarily empty

    bool createFromDegreeSequence(const DegreeSequence &d) {

        // Havel-Hakimi algorithm

        unsigned int n = d.size();

        // degree, vertex index

        std::vector<std::pair<unsigned int, unsigned int>> degrees(n);

        for (unsigned int i = 0; i < n; ++i) {

            degrees[i].first = d[i];

            degrees[i].second = i;

        }

        // Clear the graph

        reset(n);

        while (!degrees.empty()) {

            std::sort(degrees.begin(), degrees.end());

            // Highest degree is at back of the vector

            // Take it out

            unsigned int degree = degrees.back().first;

            unsigned int u = degrees.back().second;

            degrees.pop_back();

            if (degree > degrees.size()) {

                return false;

            }

            // Now loop over the last 'degree' entries of degrees

            auto rit = degrees.rbegin();

            for (unsigned int i = 0; i < degree; ++i) {

                if (rit->first == 0 || !addEdge({u, rit->second})) {

                    return false;

                }

                rit->first--;

                ++rit;

            }

        }

        return true;

    }

    DegreeSequence getDegreeSequence() const {

        DegreeSequence d(adj.size());

        std::transform(adj.begin(), adj.end(), d.begin(),

                       [](const auto &u) { return u.size(); });

        return d;

    }

    // Assumes valid vertex indices

    bool hasEdge(const Edge& e_) const {

        return badj[e_.u][e_.v];

        //Edge e;

        //if (adj[e_.u].size() <= adj[e_.v].size()) {

        //    e = e_;

        //} else {

        //    e.u = e_.v;

        //    e.v = e_.u;

        //}

        //for (unsigned int v : adj[e.u]) {

        //    if (v == e.v)

        //        return true;

        //}

        //return false;

    }

    bool addEdge(const Edge &e) {

        if (e.u >= adj.size() || e.v >= adj.size())

            return false;

        if (hasEdge(e))

            return false;

        StoredEdge se;

        se.e = e;

        se.u2vindex = adj[e.u].size();

        se.v2uindex = adj[e.v].size();

        adj[e.u].push_back(e.v);

        adj[e.v].push_back(e.u);

        edges.push_back(se);

        badj[e.u][e.v] = 1;

        badj[e.v][e.u] = 1;

        return true;

    }

    // There are two possible edge exchanges

    // switchType indicates which one is desired

    // Returns false if the switch is not possible

    bool exchangeEdges(unsigned int e1index, unsigned int e2index, bool switchType) {

        StoredEdge &se1 = edges[e1index];

        StoredEdge &se2 = edges[e2index];

        const Edge &e1 = se1.e;

        const Edge &e2 = se2.e;

        // The new edges configuration is one of these two

        // A) e1.u - e2.u and e1.v - e2.v

        // B) e1.u - e2.v and e2.u - e1.v

        // Note that to do (B) instead of (A), simply swap e2.u <-> e2.v

        // Now we can just consider switch type (A)

        if (switchType) {

            std::swap(se2.e.u, se2.e.v);

            std::swap(se2.u2vindex, se2.v2uindex);

        }

        // First check if the move is possible

        if (hasEdge({e1.u, e2.u}) || hasEdge({e1.v, e2.v}))

            return false; // conflicting edges

        // Clear old edges

        badj[e1.u][e1.v] = false;

        badj[e1.v][e1.u] = false;

        badj[e2.u][e2.v] = false;

        badj[e2.v][e2.u] = false;

        adj[e1.u][se1.u2vindex] = e2.u;

        adj[e1.v][se1.v2uindex] = e2.v;

        adj[e2.u][se2.u2vindex] = e1.u;

        adj[e2.v][se2.v2uindex] = e1.v;

        // Carefull: when updating se1,se2 also e1 and 2e change

        std::swap(se1.e.v, se2.e.u);

        std::swap(se1.v2uindex, se2.u2vindex);

        // e1 and e2 now contain the NEW edges!!

        badj[e1.u][e1.v] = true;

        badj[e1.v][e1.u] = true;

        badj[e2.u][e2.v] = true;

        badj[e2.v][e2.u] = true;

        return true;

    }

    int countTriangles() const {

        int triangles = 0;

        for (auto& v : adj) {

            for (unsigned int i = 0; i < v.size(); ++i) {

                for (unsigned int j = i + 1; j < v.size(); ++j) {

                    if (hasEdge({v[i], v[j]})) {

                        ++triangles;

                    }

                }

            }

        }

        assert(triangles % 3 == 0);

        return triangles / 3;

    }

    // Should return zero

    int consistencyCheck() const {

        // Check if info in 'edges' is present

        // in adj and badj

        for (auto &se : edges) {

            if (se.e.u >= adj.size() || se.e.v >= adj.size())

                return 1;

            if (!badj[se.e.u][se.e.v])

                return 2;

            if (!badj[se.e.v][se.e.u])

                return 3;

            if (se.u2vindex >= adj[se.e.u].size())

                return 4;

            if (se.v2uindex >= adj[se.e.v].size())

                return 5;

            if (adj[se.e.u][se.u2vindex] != se.e.v)

                return 6;

            if (adj[se.e.v][se.v2uindex] != se.e.u)

                return 7;

        }

        // Check if info in 'adj' is present

        // in badj and edges

        for (unsigned int u = 0; u < adj.size(); ++u) {

            for (unsigned int v : adj[u]) {

                if (!badj[u][v])

                    return 8;

                if (!badj[v][u])

                    return 9;

                // Check if it appears in edges

                bool found = false;

                for (auto &se : edges) {

                    if ((se.e.u == u && se.e.v == v) ||

                        (se.e.u == v && se.e.v == u)) {

                        found = true;

                        break;

                    }

                }

                if (!found)

                    return 10;

            }

        }

        // Check if info in 'badj' is present

        // in adj and edges

        // TODO

        return 0;

    }

  private:

    // Graph is saved in three formats for speed

    // They should be kept consistent at all times

    std::vector<std::vector<unsigned int>> adj;