結果

問題 No.2985 May Count Induced C4 Subgraphs
ユーザー 👑 rin204
提出日時 2024-12-10 20:17:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,185 ms / 5,000 ms
コード長 50,430 bytes
コンパイル時間 4,530 ms
コンパイル使用メモリ 305,156 KB
実行使用メモリ 118,448 KB
最終ジャッジ日時 2024-12-10 20:17:58
合計ジャッジ時間 33,847 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #define INTERACTIVE
#include <bits/stdc++.h>
using namespace std;
namespace templates {
// type
using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pil = pair<int, ll>;
using Pli = pair<ll, int>;
using Pll = pair<ll, ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
// clang-format off
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));
// clang-format on
// for loop
#define fori1(a) for (ll _ = 0; _ < (a); _++)
#define fori2(i, a) for (ll i = 0; i < (a); i++)
#define fori3(i, a, b) for (ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for (ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)
// declare and input
// clang-format off
#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define DOUBLE(...) double __VA_ARGS__; STRING(str___); __VA_ARGS__ = stod(str___);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);
// clang-format on
// const value
const ll MOD1   = 1000000007;
const ll MOD9   = 998244353;
const double PI = acos(-1);
// other macro
#if !defined(RIN__LOCAL) && !defined(INTERACTIVE)
#define endl "\n"
#endif
#define spa ' '
#define len(A) ll(A.size())
#define all(A) begin(A), end(A)
// function
vector<char> stoc(string &S) {
    int n = S.size();
    vector<char> ret(n);
    for (int i = 0; i < n; i++) ret[i] = S[i];
    return ret;
}
string ctos(vector<char> &S) {
    int n      = S.size();
    string ret = "";
    for (int i = 0; i < n; i++) ret += S[i];
    return ret;
}
template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}
template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}
template <class T, class S>
auto clamp(T &a, const S &l, const S &r) {
    return (a > r ? r : a < l ? l : a);
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chclamp(T &a, const S &l, const S &r) {
    auto b = clamp(a, l, r);
    return (a != b ? a = b, 1 : 0);
}
template <typename T>
T sum(vector<T> &A) {
    T tot = 0;
    for (auto a : A) tot += a;
    return tot;
}
template <typename T>
vector<T> compression(vector<T> X) {
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    return X;
}
// input and output
namespace io {
// __int128_t
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = std::end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) {
            --d;
            *d = '-';
        }
        int len = std::end(buffer) - d;
        if (dest.rdbuf()->sputn(d, len) != len) {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}
// vector<T>
template <typename T>
istream &operator>>(istream &is, vector<T> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << ' ';
    }
    return os;
}
// vector<vector<T>>
template <typename T>
istream &operator>>(istream &is, vector<vector<T>> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}
// pair<S, T>
template <typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &A) {
    is >> A.first >> A.second;
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, pair<S, T> &A) {
    os << A.first << ' ' << A.second;
    return os;
}
// vector<pair<S, T>>
template <typename S, typename T>
istream &operator>>(istream &is, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        is >> A[i];
    }
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}
// tuple
template <typename T, size_t N>
struct TuplePrint {
    static ostream &print(ostream &os, const T &t) {
        TuplePrint<T, N - 1>::print(os, t);
        os << ' ' << get<N - 1>(t);
        return os;
    }
};
template <typename T>
struct TuplePrint<T, 1> {
    static ostream &print(ostream &os, const T &t) {
        os << get<0>(t);
        return os;
    }
};
template <typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
    TuplePrint<decltype(t), sizeof...(Args)>::print(os, t);
    return os;
}
// io functions
void FLUSH() {
    cout << flush;
}
void print() {
    cout << endl;
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(Tail)) cout << spa;
    print(std::forward<Tail>(tail)...);
}
template <typename T, typename S>
void prisep(vector<T> &A, S sep) {
    int n = A.size();
    for (int i = 0; i < n; i++) {
        cout << A[i];
        if (i != n - 1) cout << sep;
    }
    cout << endl;
}
template <typename T, typename S>
void priend(T A, S end) {
    cout << A << end;
}
template <typename T>
void prispa(T A) {
    priend(A, spa);
}
template <typename T, typename S>
bool printif(bool f, T A, S B) {
    if (f)
        print(A);
    else
        print(B);
    return f;
}
template <class... T>
void inp(T &...a) {
    (cin >> ... >> a);
}
} // namespace io
using namespace io;
// read graph
vector<vector<int>> read_edges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<int>> edges(n, vector<int>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        u -= indexed;
        v -= indexed;
        edges[u].push_back(v);
        if (!direct) edges[v].push_back(u);
    }
    return edges;
}
vector<vector<int>> read_tree(int n, int indexed = 1) {
    return read_edges(n, n - 1, false, indexed);
}
template <typename T = long long>
vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        T w;
        inp(w);
        u -= indexed;
        v -= indexed;
        edges[u].push_back({v, w});
        if (!direct) edges[v].push_back({u, w});
    }
    return edges;
}
template <typename T = long long>
vector<vector<pair<int, T>>> read_wtree(int n, int indexed = 1) {
    return read_wedges<T>(n, n - 1, false, indexed);
}
// yes / no
namespace yesno {
// yes
inline bool yes(bool f = true) {
    cout << (f ? "yes" : "no") << endl;
    return f;
}
inline bool Yes(bool f = true) {
    cout << (f ? "Yes" : "No") << endl;
    return f;
}
inline bool YES(bool f = true) {
    cout << (f ? "YES" : "NO") << endl;
    return f;
}
// no
inline bool no(bool f = true) {
    cout << (!f ? "yes" : "no") << endl;
    return f;
}
inline bool No(bool f = true) {
    cout << (!f ? "Yes" : "No") << endl;
    return f;
}
inline bool NO(bool f = true) {
    cout << (!f ? "YES" : "NO") << endl;
    return f;
}
// possible
inline bool possible(bool f = true) {
    cout << (f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Possible(bool f = true) {
    cout << (f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool POSSIBLE(bool f = true) {
    cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}
// impossible
inline bool impossible(bool f = true) {
    cout << (!f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Impossible(bool f = true) {
    cout << (!f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool IMPOSSIBLE(bool f = true) {
    cout << (!f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}
// Alice Bob
inline bool Alice(bool f = true) {
    cout << (f ? "Alice" : "Bob") << endl;
    return f;
}
inline bool Bob(bool f = true) {
    cout << (f ? "Bob" : "Alice") << endl;
    return f;
}
// Takahashi Aoki
inline bool Takahashi(bool f = true) {
    cout << (f ? "Takahashi" : "Aoki") << endl;
    return f;
}
inline bool Aoki(bool f = true) {
    cout << (f ? "Aoki" : "Takahashi") << endl;
    return f;
}
} // namespace yesno
using namespace yesno;
} // namespace templates
using namespace templates;
/// https://nachiavivias.github.io/cp-library/cpp/graph/count-c4.html
namespace nachia {
template <class Elem>
class CsrArray {
  public:
    struct ListRange {
        using iterator = typename std::vector<Elem>::iterator;
        iterator begi, endi;
        iterator begin() const {
            return begi;
        }
        iterator end() const {
            return endi;
        }
        int size() const {
            return (int)std::distance(begi, endi);
        }
        Elem &operator[](int i) const {
            return begi[i];
        }
    };
    struct ConstListRange {
        using iterator = typename std::vector<Elem>::const_iterator;
        iterator begi, endi;
        iterator begin() const {
            return begi;
        }
        iterator end() const {
            return endi;
        }
        int size() const {
            return (int)std::distance(begi, endi);
        }
        const Elem &operator[](int i) const {
            return begi[i];
        }
    };
  private:
    int m_n;
    std::vector<Elem> m_list;
    std::vector<int> m_pos;
  public:
    CsrArray() : m_n(0), m_list(), m_pos() {}
    static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items) {
        CsrArray res;
        res.m_n = n;
        std::vector<int> buf(n + 1, 0);
        for (auto &[u, v] : items) {
            ++buf[u];
        }
        for (int i = 1; i <= n; i++) buf[i] += buf[i - 1];
        res.m_list.resize(buf[n]);
        for (int i = (int)items.size() - 1; i >= 0; i--) {
            res.m_list[--buf[items[i].first]] = std::move(items[i].second);
        }
        res.m_pos = std::move(buf);
        return res;
    }
    static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos) {
        CsrArray res;
        res.m_n    = pos.size() - 1;
        res.m_list = std::move(list);
        res.m_pos  = std::move(pos);
        return res;
    }
    ListRange operator[](int u) {
        return ListRange{m_list.begin() + m_pos[u], m_list.begin() + m_pos[u + 1]};
    }
    ConstListRange operator[](int u) const {
        return ConstListRange{m_list.begin() + m_pos[u], m_list.begin() + m_pos[u + 1]};
    }
    int size() const {
        return m_n;
    }
    int fullSize() const {
        return (int)m_list.size();
    }
};
} // namespace nachia
namespace nachia {
struct Graph {
  public:
    struct Edge {
        int from, to;
        void reverse() {
            std::swap(from, to);
        }
        int xorval() const {
            return from ^ to;
        }
    };
    Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {}
    Graph(int n, const std::vector<std::pair<int, int>> &edges, bool undirected = false)
        : m_n(n), m_isUndir(undirected) {
        m_e.resize(edges.size());
        for (std::size_t i = 0; i < edges.size(); i++) m_e[i] = {edges[i].first, edges[i].second};
    }
    template <class Cin>
    static Graph Input(Cin &cin, int n, bool undirected, int m, int offset = 0) {
        Graph res(n, undirected, m);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            res[i].from = u - offset;
            res[i].to   = v - offset;
        }
        return res;
    }
    int numVertices() const noexcept {
        return m_n;
    }
    int numEdges() const noexcept {
        return int(m_e.size());
    }
    int addNode() noexcept {
        return m_n++;
    }
    int addEdge(int from, int to) {
        m_e.push_back({from, to});
        return numEdges() - 1;
    }
    Edge &operator[](int ei) noexcept {
        return m_e[ei];
    }
    const Edge &operator[](int ei) const noexcept {
        return m_e[ei];
    }
    Edge &at(int ei) {
        return m_e.at(ei);
    }
    const Edge &at(int ei) const {
        return m_e.at(ei);
    }
    auto begin() {
        return m_e.begin();
    }
    auto end() {
        return m_e.end();
    }
    auto begin() const {
        return m_e.begin();
    }
    auto end() const {
        return m_e.end();
    }
    bool isUndirected() const noexcept {
        return m_isUndir;
    }
    void reverseEdges() noexcept {
        for (auto &e : m_e) e.reverse();
    }
    void contract(int newV, const std::vector<int> &mapping) {
        assert(numVertices() == int(mapping.size()));
        for (int i = 0; i < numVertices(); i++) assert(0 <= mapping[i] && mapping[i] < newV);
        for (auto &e : m_e) {
            e.from = mapping[e.from];
            e.to   = mapping[e.to];
        }
        m_n = newV;
    }
    std::vector<Graph> induce(int num, const std::vector<int> &mapping) const {
        int n = numVertices();
        assert(n == int(mapping.size()));
        for (int i = 0; i < n; i++) assert(-1 <= mapping[i] && mapping[i] < num);
        std::vector<int> indexV(n), newV(num);
        for (int i = 0; i < n; i++)
            if (mapping[i] >= 0) indexV[i] = newV[mapping[i]]++;
        std::vector<Graph> res;
        res.reserve(num);
        for (int i = 0; i < num; i++) res.emplace_back(newV[i], isUndirected());
        for (auto e : m_e)
            if (mapping[e.from] == mapping[e.to] && mapping[e.to] >= 0)
                res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]);
        return res;
    }
    CsrArray<int> getEdgeIndexArray(bool undirected) const {
        std::vector<std::pair<int, int>> src;
        src.reserve(numEdges() * (undirected ? 2 : 1));
        for (int i = 0; i < numEdges(); i++) {
            auto e = operator[](i);
            src.emplace_back(e.from, i);
            if (undirected) src.emplace_back(e.to, i);
        }
        return CsrArray<int>::Construct(numVertices(), src);
    }
    CsrArray<int> getEdgeIndexArray() const {
        return getEdgeIndexArray(isUndirected());
    }
    CsrArray<int> getAdjacencyArray(bool undirected) const {
        std::vector<std::pair<int, int>> src;
        src.reserve(numEdges() * (undirected ? 2 : 1));
        for (auto e : m_e) {
            src.emplace_back(e.from, e.to);
            if (undirected) src.emplace_back(e.to, e.from);
        }
        return CsrArray<int>::Construct(numVertices(), src);
    }
    CsrArray<int> getAdjacencyArray() const {
        return getAdjacencyArray(isUndirected());
    }
  private:
    int m_n;
    std::vector<Edge> m_e;
    bool m_isUndir;
};
} // namespace nachia
namespace nachia {
// simple graph
// for each edge
// O( n + m sqrt(m) ) time
template <class Weight>
std::vector<Weight> CountC4Simple(int n, Graph g, std::vector<Weight> W) {
    int m = int(W.size());
    // less incident edges, smaller index
    std::vector<int> deg(n);
    for (auto [u, v] : g) {
        deg[u]++;
        deg[v]++;
    }
    std::vector<int> I(n);
    for (int i = 0; i < n; i++) I[i] = i;
    std::sort(I.begin(), I.end(), [&](int l, int r) { return deg[l] < deg[r]; });
    {
        std::vector<int> O(n);
        for (int i = 0; i < n; i++) O[I[i]] = i;
        for (auto &[u, v] : g) {
            u = O[u], v = O[v];
        }
    }
    for (auto &e : g)
        if (e.from < e.to) e.reverse();
    // adjacency list
    std::vector<int> estart(n);
    for (int i = 0; i < n - 1; i++) estart[i + 1] = estart[i] + deg[I[i]];
    std::vector<int> eend = estart;
    std::vector<int> eid(m * 2);
    std::vector<int> eto(m * 2);
    for (int e = 0; e < m; e++) {
        auto [v, w]  = g[e];
        eid[eend[v]] = e;
        eto[eend[v]] = w;
        eend[v]++;
    }
    std::vector<int> eendx = eend;
    for (int v = 0; v < n; v++) {
        for (int i = estart[v]; i < eendx[v]; i++) {
            int e        = eid[i];
            int w        = eto[i];
            eid[eend[w]] = e;
            eto[eend[w]] = v;
            eend[w]++;
        }
    }
    std::vector<Weight> c(n); // c[x] : number of paths(v --> w --> x)
    std::vector<Weight> ans(m);
    for (int v = n - 1; v >= 0; v--) {
        for (int i = estart[v]; i < eend[v]; i++) {
            int evw = eid[i];
            int w   = eto[i];
            eend[w] -= 1; // remove w -> v
            for (int j = estart[w]; j < eend[w]; j++) {
                int ewx = eid[j];
                int x   = eto[j];
                c[x] += W[evw] * W[ewx];
            }
        }
        for (int i = estart[v]; i < eend[v]; i++) {
            int evw = eid[i];
            int w   = eto[i];
            for (int j = estart[w]; j < eend[w]; j++) {
                int ewx    = eid[j];
                int x      = eto[j];
                Weight val = c[x] - W[evw] * W[ewx];
                ans[evw] += val * W[ewx];
                ans[ewx] += val * W[evw];
            }
        }
        for (int i = estart[v]; i < eend[v]; i++) {
            int w = eto[i];
            for (int j = estart[w]; j < eend[w]; j++) c[eto[j]] = 0;
        }
    }
    return ans;
}
// for each edge
// O( n + m sqrt(m) ) time
template <class Weight>
std::vector<Weight> CountC4(int n, Graph g, std::vector<Weight> W) {
    int m = int(W.size());
    for (auto &e : g)
        if (e.to < e.from) e.reverse();
    std::vector<int> I(m);
    for (int i = 0; i < m; i++) I[i] = i;
    std::sort(I.begin(), I.end(), [&](int l, int r) {
        return g[l].from != g[r].from ? g[l].from < g[r].from : g[l].to < g[r].to;
    });
    std::vector<int> Q(m);
    Graph g2;
    int g2sz = 0;
    std::vector<Weight> W2;
    for (auto e : I) {
        if (g2sz == 0 || g2[g2sz - 1].from != g[e].from || g2[g2sz - 1].to != g[e].to) {
            g2.addEdge(g[e].from, g[e].to);
            W2.push_back(0);
            g2sz++;
        }
        W2.back() += W[e];
        Q[e] = g2sz - 1;
    }
    auto simple_res = CountC4Simple<Weight>(n, std::move(g2), std::move(W2));
    std::vector<Weight> ans(m);
    for (int e = 0; e < m; e++) ans[e] = simple_res[Q[e]];
    return ans;
}
} // namespace nachia
template <int MOD>
struct Modint {
    int x;
    Modint() : x(0) {}
    Modint(int64_t y) {
        if (y >= 0)
            x = y % MOD;
        else
            x = (y % MOD + MOD) % MOD;
    }
    Modint &operator+=(const Modint &p) {
        x += p.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    Modint &operator-=(const Modint &p) {
        x -= p.x;
        if (x < 0) x += MOD;
        return *this;
    }
    Modint &operator*=(const Modint &p) {
        x = int(1LL * x * p.x % MOD);
        return *this;
    }
    Modint &operator/=(const Modint &p) {
        *this *= p.inverse();
        return *this;
    }
    Modint &operator%=(const Modint &p) {
        assert(p.x == 0);
        return *this;
    }
    Modint operator-() const {
        return Modint(-x);
    }
    Modint &operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }
    Modint &operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }
    Modint operator++(int) {
        Modint result = *this;
        ++*this;
        return result;
    }
    Modint operator--(int) {
        Modint result = *this;
        --*this;
        return result;
    }
    friend Modint operator+(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) += rhs;
    }
    friend Modint operator-(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) -= rhs;
    }
    friend Modint operator*(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) *= rhs;
    }
    friend Modint operator/(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) /= rhs;
    }
    friend Modint operator%(const Modint &lhs, const Modint &rhs) {
        assert(rhs.x == 0);
        return Modint(lhs);
    }
    bool operator==(const Modint &p) const {
        return x == p.x;
    }
    bool operator!=(const Modint &p) const {
        return x != p.x;
    }
    bool operator<(const Modint &rhs) const {
        return x < rhs.x;
    }
    bool operator<=(const Modint &rhs) const {
        return x <= rhs.x;
    }
    bool operator>(const Modint &rhs) const {
        return x > rhs.x;
    }
    bool operator>=(const Modint &rhs) const {
        return x >= rhs.x;
    }
    Modint inverse() const {
        int a = x, b = MOD, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            a -= t * b;
            u -= t * v;
            std::swap(a, b);
            std::swap(u, v);
        }
        return Modint(u);
    }
    Modint pow(int64_t k) const {
        Modint ret(1);
        Modint y(x);
        while (k > 0) {
            if (k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }
    std::pair<int, int> to_frac(int max_n = 1000) const {
        int y = x;
        for (int i = 1; i <= max_n; i++) {
            if (y <= max_n) {
                return {y, i};
            } else if (MOD - y <= max_n) {
                return {-(MOD - y), i};
            }
            y = (y + x) % MOD;
        }
        return {-1, -1};
    }
    friend std::ostream &operator<<(std::ostream &os, const Modint &p) {
        return os << p.x;
    }
    friend std::istream &operator>>(std::istream &is, Modint &p) {
        int64_t y;
        is >> y;
        p = Modint<MOD>(y);
        return (is);
    }
    static int get_mod() {
        return MOD;
    }
};
struct Arbitrary_Modint {
    int x;
    static int MOD;
    static void set_mod(int mod) {
        MOD = mod;
    }
    Arbitrary_Modint() : x(0) {}
    Arbitrary_Modint(int64_t y) {
        if (y >= 0)
            x = y % MOD;
        else
            x = (y % MOD + MOD) % MOD;
    }
    Arbitrary_Modint &operator+=(const Arbitrary_Modint &p) {
        x += p.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    Arbitrary_Modint &operator-=(const Arbitrary_Modint &p) {
        x -= p.x;
        if (x < 0) x += MOD;
        return *this;
    }
    Arbitrary_Modint &operator*=(const Arbitrary_Modint &p) {
        x = int(1LL * x * p.x % MOD);
        return *this;
    }
    Arbitrary_Modint &operator/=(const Arbitrary_Modint &p) {
        *this *= p.inverse();
        return *this;
    }
    Arbitrary_Modint &operator%=(const Arbitrary_Modint &p) {
        assert(p.x == 0);
        return *this;
    }
    Arbitrary_Modint operator-() const {
        return Arbitrary_Modint(-x);
    }
    Arbitrary_Modint &operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }
    Arbitrary_Modint &operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }
    Arbitrary_Modint operator++(int) {
        Arbitrary_Modint result = *this;
        ++*this;
        return result;
    }
    Arbitrary_Modint operator--(int) {
        Arbitrary_Modint result = *this;
        --*this;
        return result;
    }
    friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) += rhs;
    }
    friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) -= rhs;
    }
    friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) *= rhs;
    }
    friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) /= rhs;
    }
    friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        assert(rhs.x == 0);
        return Arbitrary_Modint(lhs);
    }
    bool operator==(const Arbitrary_Modint &p) const {
        return x == p.x;
    }
    bool operator!=(const Arbitrary_Modint &p) const {
        return x != p.x;
    }
    bool operator<(const Arbitrary_Modint &rhs) {
        return x < rhs.x;
    }
    bool operator<=(const Arbitrary_Modint &rhs) {
        return x <= rhs.x;
    }
    bool operator>(const Arbitrary_Modint &rhs) {
        return x > rhs.x;
    }
    bool operator>=(const Arbitrary_Modint &rhs) {
        return x >= rhs.x;
    }
    Arbitrary_Modint inverse() const {
        int a = x, b = MOD, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            a -= t * b;
            u -= t * v;
            std::swap(a, b);
            std::swap(u, v);
        }
        return Arbitrary_Modint(u);
    }
    Arbitrary_Modint pow(int64_t k) const {
        Arbitrary_Modint ret(1);
        Arbitrary_Modint y(x);
        while (k > 0) {
            if (k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }
    friend std::ostream &operator<<(std::ostream &os, const Arbitrary_Modint &p) {
        return os << p.x;
    }
    friend std::istream &operator>>(std::istream &is, Arbitrary_Modint &p) {
        int64_t y;
        is >> y;
        p = Arbitrary_Modint(y);
        return (is);
    }
    static int get_mod() {
        return MOD;
    }
};
int Arbitrary_Modint::MOD = 998244353;
using modint9 = Modint<998244353>;
using modint1 = Modint<1000000007>;
using modint  = Arbitrary_Modint;
using mint    = modint9;
template <typename T>
struct Combination {
    int N;
    std::vector<T> fact, invfact;
    Combination(int N) : N(N) {
        fact.resize(N + 1);
        invfact.resize(N + 1);
        fact[0] = 1;
        for (int i = 1; i <= N; i++) {
            fact[i] = fact[i - 1] * i;
        }
        invfact[N] = T(1) / fact[N];
        for (int i = N - 1; i >= 0; i--) {
            invfact[i] = invfact[i + 1] * (i + 1);
        }
    }
    void extend(int n) {
        int le = fact.size();
        fact.resize(n + 1);
        invfact.resize(n + 1);
        for (int i = le; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }
        invfact[n] = T(1) / fact[n];
        for (int i = n - 1; i >= le; i--) {
            invfact[i] = invfact[i + 1] * (i + 1);
        }
    }
    T nCk(int n, int k) {
        if (k > n || k < 0) return T(0);
        if (n >= int(fact.size())) extend(n);
        return fact[n] * invfact[k] * invfact[n - k];
    }
    T nPk(int n, int k) {
        if (k > n || k < 0) return T(0);
        if (n >= int(fact.size())) extend(n);
        return fact[n] * invfact[n - k];
    }
    T nHk(int n, int k) {
        if (n == 0 && k == 0) return T(1);
        return nCk(n + k - 1, k);
    }
    T catalan(int n) {
        return nCk(2 * n, n) - nCk(2 * n, n + 1);
    }
    // n 個の +1, m 個の -1, 累積和が常にk以下
    T catalan(int n, int m, int k) {
        if (n > m + k || k < 0)
            return T(0);
        else
            return nCk(n + m, n) - nCk(n + m, m + k + 1);
    }
    // return [x^n] C^k(x)
    // 先頭に ( が k - 1 個連続するような長さ n + k - 1 の括弧列と一対一対応
    T catalan_convolution(int n, int k) {
        return catalan(k + n - 1, n, k - 1);
    }
    T narayana(int n, int k) {
        return nCk(n, k) * nCk(n, k - 1) / n;
    }
    T inv(int n) {
        assert(n >= 1);
        if (n >= int(fact.size())) extend(n);
        return invfact[n] * fact[n - 1];
    }
};
template <typename T, typename V>
struct HashMap {
    std::vector<T> key;
    std::vector<V> value;
    std::vector<bool> used;
    uint32_t mask;
    std::vector<T> keys;
    HashMap(int n = 0) {
        int s = 4;
        while (s < n) s <<= 1;
        key.resize(s);
        value.resize(s);
        used.resize(s);
        keys.reserve(s);
        mask = s - 1;
    }
    size_t size() {
        return keys.size();
    }
    size_t hash(uint64_t x) {
        static const uint64_t FIXED_RANDOM =
            std::chrono::steady_clock::now().time_since_epoch().count();
        x += FIXED_RANDOM;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        x = x ^ (x >> 31);
        return x & mask;
    }
    int index(const int64_t &x) {
        size_t i = hash(x);
        while (used[i] && key[i] != x) {
            i++;
            if (i == key.size()) i = 0;
        }
        return i;
    }
    void extend() {
        std::vector<V> values;
        values.reserve(keys.size());
        for (auto k : keys) {
            values.push_back(get(k));
        }
        int n = key.size();
        key.resize(2 * n);
        value.resize(2 * n);
        used.assign(2 * n, false);
        keys.reserve(2 * n);
        mask = 2 * n - 1;
        for (size_t i = 0; i < keys.size(); i++) {
            auto k   = index(keys[i]);
            used[k]  = true;
            key[k]   = keys[i];
            value[k] = values[i];
        }
    }
    V &operator[](const T &x) {
        if (keys.size() * 4 > key.size()) {
            extend();
        }
        int i = index(x);
        if (!used[i]) {
            used[i] = true;
            keys.push_back(x);
        }
        key[i] = x;
        return value[i];
    }
    V get(const T &x, const V &default_value = V()) {
        int i = index(x);
        return used[i] ? value[i] : default_value;
    }
    void clear() {
        keys.clear();
        used.assign(used.size(), false);
    }
};
void solve() {
    INT(n, m);
    Combination<mint> Comb(n + m + 10);
    vec(int, deg, n, 0);
    vec(Pii, E, m);
    using HM = HashMap<int, int>;
    vec(HM, E2, n);
    vvec(int, adj, n);
    fori(i, m) {
        INT(u, v);
        u--;
        v--;
        deg[u]++;
        deg[v]++;
        E[i]     = {u, v};
        E2[u][v] = 1;
        E2[v][u] = 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    /*
    0.  辺0
    1.  辺1
    2.  辺2 共有点あり
    3.  辺2 共有点なし
    4.  辺3 パス
    5.  辺3 サイクル
    6.  辺3 次数 3 あり
    7.  辺4 サイクル
    8.  辺4 C3 + 1
    9.  辺5 -1辺
    10. 辺6 K4
    */
    vector<vector<mint>> A({
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, // nC4
        {4, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0}, // 次数 0
        {0, 2, 2, 4, 2, 0, 3, 0, 1, 0, 0}, // 次数 1
        {0, 0, 1, 0, 2, 3, 0, 4, 2, 2, 0}, // 次数 2
        {0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0}, // 特定の辺の両方に隣接なし * 2
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6}, // 特定の辺の両方に隣接 * 2
        {0, 0, 0, 0, 1, 0, 3, 4, 1, 0, 0}, // 特定の辺の必ず一方だけ隣接 * 2
        {0, 1, 0, 2, 0, 3, 0, 0, 1, 1, 6}, // 特定の辺の両方に隣接する or 両方に隣接しない * 2
        {0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3}, // C4
        {0, 0, 0, 1, 1, 0, 0, 2, 1, 2, 3}, // クロス
    });
    int h = 10;
    int w = 11;
    if (false) {
        fori(i, h) {
            swap(A[i][0], A[i][w - 2]);
            swap(A[i][7], A[i][w - 1]);
        }
        fori(j, h) {
            int i1 = -1;
            fori(i, j, h) {
                if (A[i][j] != 0) {
                    i1 = i;
                    break;
                }
            }
            assert(i1 != -1);
            swap(A[j], A[i1]);
            mint inv = mint(1) / A[j][j];
            fori(k, w) {
                A[j][k] *= inv;
            }
            fori(i, h) {
                if (i == j) continue;
                mint x = A[i][j];
                fori(k, w) {
                    A[i][k] -= A[j][k] * x;
                }
            }
        }
        print(A);
        return;
    }
    vec(mint, B, h);
    B[0] = Comb.nCk(n, 4);
    fori(i, n) {
        ll c = deg[i];
        ll d = n - 1 - c;
        B[1] += Comb.nCk(c, 0) * Comb.nCk(d, 3);
        B[2] += Comb.nCk(c, 1) * Comb.nCk(d, 2);
        B[3] += Comb.nCk(c, 2) * Comb.nCk(d, 1);
    }
    for (auto [u, v] : E) {
        if (deg[u] > deg[v]) {
            swap(u, v);
        }
        int a = 0;
        for (auto x : adj[u]) {
            if (E2[v].get(x) == 1) {
                a++;
            }
        }
        int b = (deg[u] - 1) + (deg[v] - 1) - 2 * a;
        int c = n - 2 - a - b;
        B[4] += Comb.nCk(c, 2);
        B[5] += Comb.nCk(a, 2);
        B[6] += Comb.nCk(b, 2);
        B[7] += Comb.nCk(a + c, 2);
    }
    {
        nachia::Graph g(n);
        for (auto [u, v] : E) {
            g.addEdge(u, v);
        }
        vec(mint, W, m, 1);
        auto res = nachia::CountC4(n, g, W);
        B[8]     = sum(res) / 4;
    }
    for (auto [u, v] : E) {
        B[9] += m - deg[u] - deg[v] + 1;
    }
    B[9] /= 2;
    fori(i, h) {
        swap(A[i][0], A[i][w - 2]);
        swap(A[i][7], A[i][w - 1]);
    }
    fori(j, h) {
        int i1 = -1;
        fori(i, j, h) {
            if (A[i][j] != 0) {
                i1 = i;
                break;
            }
        }
        assert(i1 != -1);
        swap(A[j], A[i1]);
        swap(B[j], B[i1]);
        mint inv = mint(1) / A[j][j];
        fori(k, w) {
            A[j][k] *= inv;
        }
        B[j] *= inv;
        fori(i, h) {
            if (i == j) continue;
            mint x = A[i][j];
            fori(k, w) {
                A[i][k] -= A[j][k] * x;
            }
            B[i] -= B[j] * x;
        }
    }
    print(A[h - 1][w - 1], B[h - 1]);
}
int main() {
#ifndef INTERACTIVE
    std::cin.tie(0)->sync_with_stdio(0);
#endif
    // std::cout << std::fixed << std::setprecision(12);
    int t;
    t = 1;
    // std::cin >> t;
    while (t--) solve();
    return 0;
}
// // #pragma GCC target("avx2")
// // #pragma GCC optimize("O3")
// // #pragma GCC optimize("unroll-loops")
// // #define INTERACTIVE
//
// #include "kyopro-cpp/template.hpp"
//
// /// https://nachiavivias.github.io/cp-library/cpp/graph/count-c4.html
//
// namespace nachia {
//
// template <class Elem>
// class CsrArray {
//   public:
//     struct ListRange {
//         using iterator = typename std::vector<Elem>::iterator;
//         iterator begi, endi;
//         iterator begin() const {
//             return begi;
//         }
//         iterator end() const {
//             return endi;
//         }
//         int size() const {
//             return (int)std::distance(begi, endi);
//         }
//         Elem &operator[](int i) const {
//             return begi[i];
//         }
//     };
//     struct ConstListRange {
//         using iterator = typename std::vector<Elem>::const_iterator;
//         iterator begi, endi;
//         iterator begin() const {
//             return begi;
//         }
//         iterator end() const {
//             return endi;
//         }
//         int size() const {
//             return (int)std::distance(begi, endi);
//         }
//         const Elem &operator[](int i) const {
//             return begi[i];
//         }
//     };
//
//   private:
//     int m_n;
//     std::vector<Elem> m_list;
//     std::vector<int> m_pos;
//
//   public:
//     CsrArray() : m_n(0), m_list(), m_pos() {}
//     static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items) {
//         CsrArray res;
//         res.m_n = n;
//         std::vector<int> buf(n + 1, 0);
//         for (auto &[u, v] : items) {
//             ++buf[u];
//         }
//         for (int i = 1; i <= n; i++) buf[i] += buf[i - 1];
//         res.m_list.resize(buf[n]);
//         for (int i = (int)items.size() - 1; i >= 0; i--) {
//             res.m_list[--buf[items[i].first]] = std::move(items[i].second);
//         }
//         res.m_pos = std::move(buf);
//         return res;
//     }
//     static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos) {
//         CsrArray res;
//         res.m_n    = pos.size() - 1;
//         res.m_list = std::move(list);
//         res.m_pos  = std::move(pos);
//         return res;
//     }
//     ListRange operator[](int u) {
//         return ListRange{m_list.begin() + m_pos[u], m_list.begin() + m_pos[u + 1]};
//     }
//     ConstListRange operator[](int u) const {
//         return ConstListRange{m_list.begin() + m_pos[u], m_list.begin() + m_pos[u + 1]};
//     }
//     int size() const {
//         return m_n;
//     }
//     int fullSize() const {
//         return (int)m_list.size();
//     }
// };
//
// } // namespace nachia
//
// namespace nachia {
//
// struct Graph {
//   public:
//     struct Edge {
//         int from, to;
//         void reverse() {
//             std::swap(from, to);
//         }
//         int xorval() const {
//             return from ^ to;
//         }
//     };
//     Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected)
//     {} Graph(int n, const std::vector<std::pair<int, int>> &edges, bool undirected = false)
//         : m_n(n), m_isUndir(undirected) {
//         m_e.resize(edges.size());
//         for (std::size_t i = 0; i < edges.size(); i++) m_e[i] = {edges[i].first,
//         edges[i].second};
//     }
//     template <class Cin>
//     static Graph Input(Cin &cin, int n, bool undirected, int m, int offset = 0) {
//         Graph res(n, undirected, m);
//         for (int i = 0; i < m; i++) {
//             int u, v;
//             cin >> u >> v;
//             res[i].from = u - offset;
//             res[i].to   = v - offset;
//         }
//         return res;
//     }
//     int numVertices() const noexcept {
//         return m_n;
//     }
//     int numEdges() const noexcept {
//         return int(m_e.size());
//     }
//     int addNode() noexcept {
//         return m_n++;
//     }
//     int addEdge(int from, int to) {
//         m_e.push_back({from, to});
//         return numEdges() - 1;
//     }
//     Edge &operator[](int ei) noexcept {
//         return m_e[ei];
//     }
//     const Edge &operator[](int ei) const noexcept {
//         return m_e[ei];
//     }
//     Edge &at(int ei) {
//         return m_e.at(ei);
//     }
//     const Edge &at(int ei) const {
//         return m_e.at(ei);
//     }
//     auto begin() {
//         return m_e.begin();
//     }
//     auto end() {
//         return m_e.end();
//     }
//     auto begin() const {
//         return m_e.begin();
//     }
//     auto end() const {
//         return m_e.end();
//     }
//     bool isUndirected() const noexcept {
//         return m_isUndir;
//     }
//     void reverseEdges() noexcept {
//         for (auto &e : m_e) e.reverse();
//     }
//     void contract(int newV, const std::vector<int> &mapping) {
//         assert(numVertices() == int(mapping.size()));
//         for (int i = 0; i < numVertices(); i++) assert(0 <= mapping[i] && mapping[i] < newV);
//         for (auto &e : m_e) {
//             e.from = mapping[e.from];
//             e.to   = mapping[e.to];
//         }
//         m_n = newV;
//     }
//     std::vector<Graph> induce(int num, const std::vector<int> &mapping) const {
//         int n = numVertices();
//         assert(n == int(mapping.size()));
//         for (int i = 0; i < n; i++) assert(-1 <= mapping[i] && mapping[i] < num);
//         std::vector<int> indexV(n), newV(num);
//         for (int i = 0; i < n; i++)
//             if (mapping[i] >= 0) indexV[i] = newV[mapping[i]]++;
//         std::vector<Graph> res;
//         res.reserve(num);
//         for (int i = 0; i < num; i++) res.emplace_back(newV[i], isUndirected());
//         for (auto e : m_e)
//             if (mapping[e.from] == mapping[e.to] && mapping[e.to] >= 0)
//                 res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]);
//         return res;
//     }
//     CsrArray<int> getEdgeIndexArray(bool undirected) const {
//         std::vector<std::pair<int, int>> src;
//         src.reserve(numEdges() * (undirected ? 2 : 1));
//         for (int i = 0; i < numEdges(); i++) {
//             auto e = operator[](i);
//             src.emplace_back(e.from, i);
//             if (undirected) src.emplace_back(e.to, i);
//         }
//         return CsrArray<int>::Construct(numVertices(), src);
//     }
//     CsrArray<int> getEdgeIndexArray() const {
//         return getEdgeIndexArray(isUndirected());
//     }
//     CsrArray<int> getAdjacencyArray(bool undirected) const {
//         std::vector<std::pair<int, int>> src;
//         src.reserve(numEdges() * (undirected ? 2 : 1));
//         for (auto e : m_e) {
//             src.emplace_back(e.from, e.to);
//             if (undirected) src.emplace_back(e.to, e.from);
//         }
//         return CsrArray<int>::Construct(numVertices(), src);
//     }
//     CsrArray<int> getAdjacencyArray() const {
//         return getAdjacencyArray(isUndirected());
//     }
//
//   private:
//     int m_n;
//     std::vector<Edge> m_e;
//     bool m_isUndir;
// };
//
// } // namespace nachia
//
// namespace nachia {
//
// // simple graph
// // for each edge
// // O( n + m sqrt(m) ) time
// template <class Weight>
// std::vector<Weight> CountC4Simple(int n, Graph g, std::vector<Weight> W) {
//     int m = int(W.size());
//
//     // less incident edges, smaller index
//     std::vector<int> deg(n);
//     for (auto [u, v] : g) {
//         deg[u]++;
//         deg[v]++;
//     }
//     std::vector<int> I(n);
//     for (int i = 0; i < n; i++) I[i] = i;
//     std::sort(I.begin(), I.end(), [&](int l, int r) { return deg[l] < deg[r]; });
//     {
//         std::vector<int> O(n);
//         for (int i = 0; i < n; i++) O[I[i]] = i;
//         for (auto &[u, v] : g) {
//             u = O[u], v = O[v];
//         }
//     }
//
//     for (auto &e : g)
//         if (e.from < e.to) e.reverse();
//
//     // adjacency list
//
//     std::vector<int> estart(n);
//     for (int i = 0; i < n - 1; i++) estart[i + 1] = estart[i] + deg[I[i]];
//     std::vector<int> eend = estart;
//     std::vector<int> eid(m * 2);
//     std::vector<int> eto(m * 2);
//
//     for (int e = 0; e < m; e++) {
//         auto [v, w]  = g[e];
//         eid[eend[v]] = e;
//         eto[eend[v]] = w;
//         eend[v]++;
//     }
//     std::vector<int> eendx = eend;
//     for (int v = 0; v < n; v++) {
//         for (int i = estart[v]; i < eendx[v]; i++) {
//             int e        = eid[i];
//             int w        = eto[i];
//             eid[eend[w]] = e;
//             eto[eend[w]] = v;
//             eend[w]++;
//         }
//     }
//
//     std::vector<Weight> c(n); // c[x] : number of paths(v --> w --> x)
//     std::vector<Weight> ans(m);
//     for (int v = n - 1; v >= 0; v--) {
//         for (int i = estart[v]; i < eend[v]; i++) {
//             int evw = eid[i];
//             int w   = eto[i];
//             eend[w] -= 1; // remove w -> v
//             for (int j = estart[w]; j < eend[w]; j++) {
//                 int ewx = eid[j];
//                 int x   = eto[j];
//                 c[x] += W[evw] * W[ewx];
//             }
//         }
//         for (int i = estart[v]; i < eend[v]; i++) {
//             int evw = eid[i];
//             int w   = eto[i];
//             for (int j = estart[w]; j < eend[w]; j++) {
//                 int ewx    = eid[j];
//                 int x      = eto[j];
//                 Weight val = c[x] - W[evw] * W[ewx];
//                 ans[evw] += val * W[ewx];
//                 ans[ewx] += val * W[evw];
//             }
//         }
//         for (int i = estart[v]; i < eend[v]; i++) {
//             int w = eto[i];
//             for (int j = estart[w]; j < eend[w]; j++) c[eto[j]] = 0;
//         }
//     }
//     return ans;
// }
//
// // for each edge
// // O( n + m sqrt(m) ) time
// template <class Weight>
// std::vector<Weight> CountC4(int n, Graph g, std::vector<Weight> W) {
//     int m = int(W.size());
//     for (auto &e : g)
//         if (e.to < e.from) e.reverse();
//     std::vector<int> I(m);
//     for (int i = 0; i < m; i++) I[i] = i;
//     std::sort(I.begin(), I.end(), [&](int l, int r) {
//         return g[l].from != g[r].from ? g[l].from < g[r].from : g[l].to < g[r].to;
//     });
//
//     std::vector<int> Q(m);
//     Graph g2;
//     int g2sz = 0;
//     std::vector<Weight> W2;
//     for (auto e : I) {
//         if (g2sz == 0 || g2[g2sz - 1].from != g[e].from || g2[g2sz - 1].to != g[e].to) {
//             g2.addEdge(g[e].from, g[e].to);
//             W2.push_back(0);
//             g2sz++;
//         }
//         W2.back() += W[e];
//         Q[e] = g2sz - 1;
//     }
//
//     auto simple_res = CountC4Simple<Weight>(n, std::move(g2), std::move(W2));
//     std::vector<Weight> ans(m);
//     for (int e = 0; e < m; e++) ans[e] = simple_res[Q[e]];
//     return ans;
// }
//
// } // namespace nachia
//
// #include "misc/Modint.hpp"
// using mint = modint9;
// #include "math/Combination.hpp"
//
// #include "misc/HashMap.hpp"
//
// void solve() {
//     INT(n, m);
//     Combination<mint> Comb(n + m + 10);
//     vec(int, deg, n, 0);
//     vec(Pii, E, m);
//     using HM = HashMap<int, int>;
//     vec(HM, E2, n);
//     vvec(int, adj, n);
//     fori(i, m) {
//         INT(u, v);
//         u--;
//         v--;
//         deg[u]++;
//         deg[v]++;
//         E[i]     = {u, v};
//         E2[u][v] = 1;
//         E2[v][u] = 1;
//         adj[u].push_back(v);
//         adj[v].push_back(u);
//     }
//
//     /*
//     0.  辺0
//     1.  辺1
//     2.  辺2 共有点あり
//     3.  辺2 共有点なし
//     4.  辺3 パス
//     5.  辺3 サイクル
//     6.  辺3 次数 3 あり
//     7.  辺4 サイクル
//     8.  辺4 C3 + 1
//     9.  辺5 -1辺
//     10. 辺6 K4
//     */
//
//     vector<vector<mint>> A({
//         {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, // nC4
//         {4, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0}, // 次数 0
//         {0, 2, 2, 4, 2, 0, 3, 0, 1, 0, 0}, // 次数 1
//         {0, 0, 1, 0, 2, 3, 0, 4, 2, 2, 0}, // 次数 2
//         {0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0}, // 特定の辺の両方に隣接なし * 2
//         {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6}, // 特定の辺の両方に隣接 * 2
//         {0, 0, 0, 0, 1, 0, 3, 4, 1, 0, 0}, // 特定の辺の必ず一方だけ隣接 * 2
//         {0, 1, 0, 2, 0, 3, 0, 0, 1, 1, 6}, // 特定の辺の両方に隣接する or 両方に隣接しない * 2
//         {0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3}, // C4
//         {0, 0, 0, 1, 1, 0, 0, 2, 1, 2, 3}, // クロス
//     });
//
//     int h = 10;
//     int w = 11;
//     if (false) {
//         fori(i, h) {
//             swap(A[i][0], A[i][w - 2]);
//             swap(A[i][7], A[i][w - 1]);
//         }
//         fori(j, h) {
//             int i1 = -1;
//             fori(i, j, h) {
//                 if (A[i][j] != 0) {
//                     i1 = i;
//                     break;
//                 }
//             }
//             assert(i1 != -1);
//             swap(A[j], A[i1]);
//             mint inv = mint(1) / A[j][j];
//             fori(k, w) {
//                 A[j][k] *= inv;
//             }
//
//             fori(i, h) {
//                 if (i == j) continue;
//                 mint x = A[i][j];
//                 fori(k, w) {
//                     A[i][k] -= A[j][k] * x;
//                 }
//             }
//         }
//         print(A);
//         return;
//     }
//
//     vec(mint, B, h);
//     B[0] = Comb.nCk(n, 4);
//     fori(i, n) {
//         ll c = deg[i];
//         ll d = n - 1 - c;
//         B[1] += Comb.nCk(c, 0) * Comb.nCk(d, 3);
//         B[2] += Comb.nCk(c, 1) * Comb.nCk(d, 2);
//         B[3] += Comb.nCk(c, 2) * Comb.nCk(d, 1);
//     }
//
//     for (auto [u, v] : E) {
//         if (deg[u] > deg[v]) {
//             swap(u, v);
//         }
//         int a = 0;
//         for (auto x : adj[u]) {
//             if (E2[v].get(x) == 1) {
//                 a++;
//             }
//         }
//         int b = (deg[u] - 1) + (deg[v] - 1) - 2 * a;
//         int c = n - 2 - a - b;
//
//         B[4] += Comb.nCk(c, 2);
//         B[5] += Comb.nCk(a, 2);
//         B[6] += Comb.nCk(b, 2);
//         B[7] += Comb.nCk(a + c, 2);
//     }
//
//     {
//         nachia::Graph g(n);
//         for (auto [u, v] : E) {
//             g.addEdge(u, v);
//         }
//
//         vec(mint, W, m, 1);
//         auto res = nachia::CountC4(n, g, W);
//         B[8]     = sum(res) / 4;
//     }
//
//     for (auto [u, v] : E) {
//         B[9] += m - deg[u] - deg[v] + 1;
//     }
//     B[9] /= 2;
//
//     fori(i, h) {
//         swap(A[i][0], A[i][w - 2]);
//         swap(A[i][7], A[i][w - 1]);
//     }
//
//     fori(j, h) {
//         int i1 = -1;
//         fori(i, j, h) {
//             if (A[i][j] != 0) {
//                 i1 = i;
//                 break;
//             }
//         }
//         assert(i1 != -1);
//         swap(A[j], A[i1]);
//         swap(B[j], B[i1]);
//         mint inv = mint(1) / A[j][j];
//         fori(k, w) {
//             A[j][k] *= inv;
//         }
//         B[j] *= inv;
//
//         fori(i, h) {
//             if (i == j) continue;
//             mint x = A[i][j];
//             fori(k, w) {
//                 A[i][k] -= A[j][k] * x;
//             }
//             B[i] -= B[j] * x;
//         }
//     }
//
//     print(A[h - 1][w - 1], B[h - 1]);
// }
//
// int main() {
// #ifndef INTERACTIVE
//     std::cin.tie(0)->sync_with_stdio(0);
// #endif
//     // std::cout << std::fixed << std::setprecision(12);
//     int t;
//     t = 1;
//     // std::cin >> t;
//     while (t--) solve();
//     return 0;
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0