結果
| 問題 | 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 |
ソースコード
// #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;
// }