結果
| 問題 |
No.2428 Returning Shuffle
|
| コンテスト | |
| ユーザー |
 Gandalfr
|
| 提出日時 | 2023-08-18 22:48:31 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,043 ms / 2,000 ms |
| コード長 | 43,428 bytes |
| コンパイル時間 | 2,651 ms |
| コンパイル使用メモリ | 238,548 KB |
| 最終ジャッジ日時 | 2025-02-16 10:31:41 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
#line 1 "playspace/main.cpp"
#include <bits/stdc++.h>
#line 8 "library/gandalfr/other/io_supporter.hpp"
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++)
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &st) {
for (const T &x : st) {
std::cout << x << " ";
}
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::multiset<T> &st) {
for (const T &x : st) {
std::cout << x << " ";
}
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::deque<T> &dq) {
for (const T &x : dq) {
std::cout << x << " ";
}
return os;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
os << p.first << ' ' << p.second;
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, std::queue<T> &q) {
int sz = q.size();
while (--sz) {
os << q.front() << ' ';
q.push(q.front());
q.pop();
}
os << q.front();
q.push(q.front());
q.pop();
return os;
}
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
for (T &in : v)
is >> in;
return is;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
#line 8 "library/gandalfr/graph/graph.hpp"
#line 3 "library/gandalfr/data_structure/union_find.hpp"
#line 6 "library/gandalfr/data_structure/union_find.hpp"
class union_find {
private:
int N;
mutable std::vector<int> par;
std::vector<int> nxt;
int group_num; // 集合の数
public:
union_find() : N(0), group_num(0) {}
union_find(int n) : N(n), par(n, -1), nxt(n), group_num(n) {
std::iota(nxt.begin(), nxt.end(), 0);
}
/**
* @brief 頂点を n 個に増やす
* @attention 小さくはできない
*/
void expand(int n) {
if (n <= N)
return;
par.resize(n, -1);
nxt.resize(n);
for (int i = N; i < n; ++i)
nxt[i] = i;
group_num += n - N;
N = n;
}
int leader(int x) const {
return (par[x] < 0 ? x : par[x] = leader(par[x]));
}
bool same(int x, int y) const { return leader(x) == leader(y); }
bool merge(int x, int y) {
if ((x = leader(x)) == (y = leader(y)))
return false;
if (-par[x] > -par[y])
std::swap(x, y);
par[x] += par[y];
par[y] = x;
std::swap(nxt[x], nxt[y]);
group_num--;
return true;
}
/**
* @brief x の属するグループのサイズを返す
*/
int size(int x) const { return -par[leader(x)]; }
/**
* @brief すべてのノードの数
*/
int size() const { return N; }
std::vector<int> contained_group(int x) const {
std::vector<int> ret{x};
for (int cu = nxt[x]; cu != ret[0]; cu = nxt[cu])
ret.push_back(cu);
return ret;
}
int count_groups() const { return group_num; }
std::vector<std::vector<int>> all_groups() const {
std::vector<std::vector<int>> result;
result.reserve(group_num);
std::vector<bool> used(N, false);
for (int i = 0; i < N; ++i) {
if (!used[i]) {
result.emplace_back(contained_group(i));
for (int x : result.back()) {
used[x] = true;
}
}
}
return result;
}
};
#line 3 "library/gandalfr/math/matrix.hpp"
#line 8 "library/gandalfr/math/matrix.hpp"
template <class T> class matrix {
private:
int H, W;
std::valarray<std::valarray<T>> table;
enum rowtrans_operation_name { SCALE, SWAP, ADD };
struct rowtrans_operation {
int op, tar, res;
T scl;
};
using operations_history = std::vector<rowtrans_operation>;
public:
matrix() = default;
matrix(int _H, int _W, T val = 0)
: H(_H), W(_W), table(std::valarray<T>(val, _W), _H) {}
matrix(const std::vector<std::vector<T>> &vv)
: H(vv.size()), W(vv[0].size()), table(std::valarray<T>(W), H) {
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
table[i][j] = vv[i][j];
}
matrix(const std::valarray<std::valarray<T>> &vv)
: H(vv.size()), W(vv[0].size()), table(vv) {}
/**
* @brief 行列をリサイズする。
* @param val 拡張部分の値
*/
void resize(int _H, int _W, T val = 0) {
H = _H, W = _W;
table.resize(_H, std::valarray<T>(val, _H));
}
int size_H() const { return H; }
int size_W() const { return W; }
void transpose() {
matrix<T> ret(W, H);
for (int i = 0; i < H; i++)
for (int j = 0; j < W; j++)
ret.table[j][i] = table[i][j];
*this = std::move(ret);
}
void row_assign(int i, const std::valarray<T> &row) {
assert(W == (int)row.size());
table[i] = std::move(row);
}
void row_swap(int i, int j) {
assert(0 <= i && i < H);
assert(0 <= j && j < H);
table[i].swap(table[j]);
}
/**
* @attention O(n^3)
* @attention 整数型では正しく計算できない。double や fraction を使うこと。
* @attention 枢軸選びをしていないので double では誤差が出るかも。
*/
operations_history sweep_method() {
operations_history hist;
T ret = 1;
for (int h = 0, w = 0; h < H && w < W; w++) {
if (table[h][w] == 0) {
for (int piv = h + 1; piv < H; piv++) {
if (table[piv][w] != 0) {
hist.push_back({SWAP, h, piv, 0});
row_swap(h, piv);
break;
}
}
if (table[h][w] == 0) {
continue;
}
}
T inv = 1 / table[h][w];
hist.push_back({SCALE, -1, w, inv});
table[h] *= inv;
for (int j = h + 1; j < H; j++) {
hist.push_back({ADD, h, j, -table[j][w]});
table[j] -= table[h] * table[j][w];
}
h++;
}
return hist;
}
int rank() {
auto U(*this);
U.sweep_method();
int r = 0;
for (int i = 0; i < H; ++i) {
for (int j = i; j < W; ++j) {
if (U.table[i][j] != 0) {
r++;
break;
}
}
}
return r;
}
T determinant() const {
assert(H == W);
matrix<T> U(*this);
T det = 1;
auto hist = U.sweep_method();
if (U.table[H - 1][H - 1] == 0)
return 0;
for (auto &[op, tar, res, scl] : hist) {
switch (op) {
case SCALE:
det /= scl;
break;
case SWAP:
det *= -1;
break;
}
}
return det;
}
std::vector<T> solve_system_of_equations(const std::vector<T> &y) {
assert(H == W);
std::vector<T> x(y);
matrix<T> U(*this);
auto hist = U.sweep_method();
if (U.table[H - 1][H - 1] == 0)
return {};
for (auto &[op, tar, res, scl] : hist) {
switch (op) {
case SCALE:
x[res] *= scl;
break;
case SWAP:
std::swap(x[tar], x[res]);
break;
case ADD:
x[res] += x[tar] * scl;
break;
}
}
for (int i = H - 1; i >= 0; --i) {
for (int j = 0; j < i; ++j) {
x[j] -= U.table[j][i] * x[i];
}
}
return x;
}
matrix<T> inverse() {
assert(H == W);
matrix<T> INV(matrix<T>::E(H)), U(*this);
auto hist = U.sweep_method();
if (U.table[H - 1][H - 1] == 0)
return matrix<T>(0, 0);
for (auto &[op, tar, res, scl] : hist) {
switch (op) {
case SCALE:
INV.table[res] *= scl;
break;
case SWAP:
std::swap(INV.table[tar], INV.table[res]);
break;
case ADD:
INV.table[res] += INV.table[tar] * scl;
break;
}
}
for (int i = H - 1; i >= 0; --i) {
for (int j = 0; j < i; ++j) {
INV.table[j] -= INV.table[i] * U.table[j][i];
}
}
return INV;
}
void print() const {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
std::cout << table[i][j] << (j == W - 1 ? "" : " ");
}
std::cout << std::endl;
}
}
matrix<T> &operator+=(const matrix<T> &a) {
this->table += a.table;
return *this;
}
matrix<T> &operator-=(const matrix<T> &a) {
this->table -= a.table;
return *this;
}
matrix<T> &operator*=(const T &a) {
this->table *= a;
return *this;
}
matrix<T> &operator*=(const matrix<T> &a) {
assert(W == a.H);
matrix<T> a_t(a), ret(H, a.W);
a_t.transpose();
for (int i = 0; i < H; i++) {
for (int j = 0; j < a_t.H; j++) {
ret.table[i][j] = (table[i] * a_t.table[j]).sum();
}
}
*this = std::move(ret);
return *this;
}
matrix<T> &operator/=(const T &a) {
this->table /= a;
return *this;
}
/**
* @brief 行列の冪乗。
* @param n 指数
* @attention n が 0 なら単位行列。
* @attention 演算子の優先度に注意。
*/
matrix<T> operator^=(long long n) {
assert(H == W);
if (n == 0)
return *this = E(H);
n--;
matrix<T> x(*this);
while (n) {
if (n & 1)
*this *= x;
x *= x;
n >>= 1;
}
return *this;
}
matrix<T> operator+() { return *this; }
matrix<T> operator-() { return matrix<T>(*this) *= -1; }
matrix<T> operator+(const matrix<T> &a) { return matrix<T>(*this) += a; }
matrix<T> operator-(const matrix<T> &a) { return matrix<T>(*this) -= a; }
template <typename S> matrix<T> operator*(const S &a) {
return matrix<T>(*this) *= a;
}
matrix<T> operator/(const T &a) { return matrix<T>(*this) /= a; }
matrix<T> operator^(long long n) { return matrix<T>(*this) ^= n; }
friend std::istream &operator>>(std::istream &is, matrix<T> &mt) {
for (auto &arr : mt.table)
for (auto &x : arr)
is >> x;
return is;
}
T &operator()(int h, int w) {
assert(0 <= h && h < H && 0 <= w && w <= W);
return table[h][w];
}
/**
* @brief サイズ n の単位行列。
*/
static matrix<T> E(int N) {
matrix<T> ret(N, N);
for (int i = 0; i < N; i++)
ret.table[i][i] = 1;
return ret;
}
};
#line 3 "library/gandalfr/graph/edge.hpp"
namespace internal {
template <class DERIVED, class WEIGHT> struct _base_edge {
int from;
int to;
WEIGHT cost;
int id;
_base_edge() {}
_base_edge(int _from, int _to, WEIGHT _cost, int _id)
: from(_from), to(_to), cost(_cost), id(_id) {}
friend bool operator>(const _base_edge &e1, const _base_edge &e) {
return e1.compare(e) > 0;
}
friend bool operator>=(const _base_edge &e1, const _base_edge &e) {
return e1.compare(e) >= 0;
}
friend bool operator<(const _base_edge &e1, const _base_edge &e) {
return e1.compare(e) < 0;
}
friend bool operator<=(const _base_edge &e1, const _base_edge &e) {
return e1.compare(e) <= 0;
}
friend std::ostream &operator<<(std::ostream &os,
const _base_edge<DERIVED, WEIGHT> &e) {
e.print(os);
return os;
}
_base_edge &operator=(const _base_edge &e) = default;
virtual ~_base_edge() = default;
DERIVED minmax() const {
auto [f, t] = std::minmax(from, to);
return {f, t, cost, id};
}
DERIVED reverse() const { return {to, from, cost, id}; }
operator int() const { return to; }
protected:
virtual void print(std::ostream &os) const = 0;
virtual int compare(const _base_edge &e) const = 0;
};
} // namespace internal
template <class WEIGHT>
struct edge : public internal::_base_edge<edge<WEIGHT>, WEIGHT> {
using internal::_base_edge<edge<WEIGHT>, WEIGHT>::_base_edge;
protected:
void print(std::ostream &os) const override {
os << this->from << " " << this->to << " " << this->cost;
}
int compare(
const internal::_base_edge<edge<WEIGHT>, WEIGHT> &e) const override {
if (this->cost == e.cost) {
if (this->from == e.from)
return this->to - e.to;
return this->from - e.from;
}
return this->cost - e.cost;
}
};
template <> struct edge<int> : public internal::_base_edge<edge<int>, int> {
static inline const int cost = 1;
using internal::_base_edge<edge<int>, int>::_base_edge;
edge(int _from, int _to, int _id)
: _base_edge<edge<int>, int>(_from, _to, 0, _id) {}
protected:
void print(std::ostream &os) const override {
os << this->from << " " << this->to;
}
int compare(const internal::_base_edge<edge<int>, int> &e) const override {
if (this->from == e.from)
return this->to - e.to;
return this->from - e.from;
}
};
#line 12 "library/gandalfr/graph/graph.hpp"
/**
* @brief グラフを管理するクラス。
* @tparam WEIGHT int なら重みなし、そうでないなら重みつきグラフ
* @tparam is_directed 有向グラフかとうか
*/
template <typename WEIGHT, bool is_directed> class graph {
private:
int N;
std::vector<std::vector<edge<WEIGHT>>> G;
std::vector<edge<WEIGHT>> E;
union_find uf;
WEIGHT W = 0;
mutable std::vector<bool> visited; // dfs / bfs のための領域
bool forest_flag = true;
const WEIGHT WEIGHT_MAX = std::numeric_limits<WEIGHT>::max();
void reset_visited_flag(int node) const {
for (int x : uf.contained_group(node))
visited[x] = false;
}
void reset_visited_flag() const { visited.assign(N, false); }
public:
graph() : N(0){};
graph(int n) : N(n), G(n), uf(n), visited(n){};
/**
* @brief ノードの数をn個まで増やす
* @param n サイズ
* @attention 今のノード数より小さい数を渡したとき、変化なし
*/
void expand(int n) {
if (n <= N)
return;
N = n;
G.resize(n);
visited.resize(n);
uf.expand(n);
}
/**
* @return ノードの数
*/
int count_nodes() const { return N; }
/**
* @return 辺の数
*/
int count_edges() const { return E.size(); }
/**
* @param n ノード番号
* @return ノード n からの隣接頂点のリストの const 参照
*/
const std::vector<edge<WEIGHT>> &operator[](int n) const { return G[n]; }
/**
* @return グラフ全体の辺のリストの const 参照
*/
const std::vector<edge<WEIGHT>> &edges() const { return E; }
/**
* @param x ノード番号
* @param y ノード番号
* @return x, y が連結かどうか
*/
bool are_connected(int x, int y) const { return uf.same(x, y); }
/**
* @return 連結成分の数
*/
int count_connected_components() const { return uf.count_groups(); }
/**
* @return 連結成分のリストのリスト
*/
std::vector<std::vector<int>> weakly_connected_components() const {
return uf.all_groups();
}
/**
* @return 木か
*/
bool is_tree() const { return forest_flag && uf.count_groups() == 1; }
/**
* @return 森か
*/
bool is_forest() const { return forest_flag; }
/**
* @return グラフの重み
*/
WEIGHT weight() const { return W; }
/**
* @param e 辺
* @attention 渡した辺の id は保持される
*/
void add_edge(const edge<WEIGHT> &e) {
forest_flag &= uf.merge(e.from, e.to);
G[e.from].emplace_back(e);
if (!is_directed && e.from != e.to)
G[e.to].emplace_back(e.reverse());
if constexpr (is_directed) {
E.emplace_back(e);
} else {
E.emplace_back(e.minmax());
}
W += e.cost;
}
/**
* @attention 辺の id は、(現在の辺の本数)番目 が振られる
* @attention WEIGHT が int だとエラー
*/
void add_edge(int from, int to, WEIGHT cost) {
static_assert(!std::is_same<WEIGHT, int>::value);
add_edge({from, to, cost, (int)E.size()});
}
/**
* @attention 辺の id は、(現在の辺の本数)番目 が振られる
* @attention WEIGHT が int 以外だとエラー
*/
void add_edge(int from, int to) {
static_assert(std::is_same<WEIGHT, int>::value);
add_edge({from, to, (int)E.size()});
}
/**
* @brief グラフを連結なグラフに分けてリストにして返す
* @example auto[Gs, gr, nd] = G.decompose();
* @returns
* 1.グラフのリスト
* 2.各ノードがグラフのリストの何番目に属するか
* 3.各ノードがグラフのどのノードになっているか
*/
std::tuple<std::vector<graph>, std::vector<int>, std::vector<int>>
decompose() const {
std::vector<graph> Gs(uf.count_groups());
std::vector<std::vector<int>> groups(uf.all_groups());
std::vector<int> group_id(N), node_id(N);
for (int i = 0; i < (int)groups.size(); i++) {
Gs[i].expand(groups[i].size());
for (int j = 0; j < (int)groups[i].size(); j++) {
group_id[groups[i][j]] = i;
node_id[groups[i][j]] = j;
}
}
for (auto e : E) {
int id = group_id[e.from];
e.from = node_id[e.from];
e.to = node_id[e.to];
Gs[id].add_edge(e);
}
return std::make_tuple(std::move(Gs), std::move(group_id),
std::move(node_id));
}
/**
* @brief グラフを隣接行列に変換
* @param invalid 辺のないときの値
* @attention 自己ループが含まれていない限り、対角成分は 0
* @attention 多重辺を持たないと仮定
*/
matrix<WEIGHT> to_adjajency(WEIGHT invalid = 0) const {
matrix<WEIGHT> ret(N, N, invalid);
for (int i = 0; i < N; i++)
ret(i, i) = 0;
for (int i = 0; i < N; i++)
for (auto &e : G[i])
ret(i, e.to) = e.cost;
return ret;
}
/**
* @brief 行きがけ順に bfs
*/
std::vector<int> preorder(int start) const {
std::vector<int> result;
std::stack<std::pair<int, int>> stk;
reset_visited_flag(start);
visited[start] = true;
stk.push({start, 0});
while (!stk.empty()) {
auto &[cu, idx] = stk.top();
if (idx == 0)
result.push_back(cu);
if (idx == G[cu].size()) {
stk.pop();
} else {
int to = G[cu][idx++];
if (!visited[to]) {
visited[to] = true;
stk.push({to, 0});
}
}
}
return result;
}
/**
* @brief 通りがけ順に bfs
*/
std::vector<int> inorder(int start) const {
std::vector<int> result;
std::stack<std::pair<int, int>> stk;
reset_visited_flag(start);
visited[start] = true;
stk.push({start, 0});
while (!stk.empty()) {
auto &[cu, idx] = stk.top();
if (idx == G[cu].size()) {
stk.pop();
result.push_back(cu);
} else {
int to = G[cu][idx++];
if (!visited[to]) {
visited[to] = true;
stk.push({to, 0});
result.push_back(cu);
}
}
}
return result;
}
/**
* @brief 帰りがけ順に bfs
*/
std::vector<int> postorder(int start) const {
std::vector<int> result;
std::stack<std::pair<int, int>> stk;
reset_visited_flag(start);
visited[start] = true;
stk.push({start, 0});
while (!stk.empty()) {
auto &[cu, idx] = stk.top();
if (idx == G[cu].size()) {
stk.pop();
result.push_back(cu);
} else {
int to = G[cu][idx++];
if (!visited[to]) {
visited[to] = true;
stk.push({to, 0});
}
}
}
return result;
}
private:
using PAIR = std::pair<WEIGHT, int>;
using Dijkstra_queue =
std::priority_queue<PAIR, std::vector<PAIR>, std::greater<PAIR>>;
void run_bfs(std::vector<int> &dist, std::queue<int> &q) const {
while (!q.empty()) {
int cu = q.front();
q.pop();
for (auto &e : G[cu]) {
if (dist[e.to] != WEIGHT_MAX)
continue;
dist[e.to] = dist[cu] + 1;
q.push(e.to);
}
}
}
void run_Dijkstra(std::vector<WEIGHT> &dist, Dijkstra_queue &q) const {
while (!q.empty()) {
WEIGHT cur_dist = q.top().first;
int cu = q.top().second;
q.pop();
if (visited[cu])
continue;
visited[cu] = true;
for (auto &e : G[cu]) {
WEIGHT alt = cur_dist + e.cost;
if (dist[e.to] <= alt)
continue;
dist[e.to] = alt;
q.push({alt, e.to});
}
}
}
public:
/**
* @brief 最短距離を計算する
* @param start_node 始点
* @param invalid 到達不能な頂点に格納される値
* @return 各ノードまでの最短距離のリスト
*/
std::vector<WEIGHT> distances(int start_node, WEIGHT invalid) const {
std::vector<WEIGHT> dist(N, WEIGHT_MAX);
dist[start_node] = 0;
if constexpr (std::is_same<WEIGHT, int>::value) {
// BFS algorithm
std::queue<int> q;
q.push(start_node);
run_bfs(dist, q);
} else {
// Dijkstra's algorithm
Dijkstra_queue q;
q.push({0, start_node});
reset_visited_flag(start_node);
run_Dijkstra(dist, q);
}
for (auto &x : dist)
if (x == WEIGHT_MAX)
x = invalid;
return dist;
}
public:
/**
* @brief 最短距離を計算する
* @param start_nodes 始点のリスト
* @param invalid 到達不能な頂点に格納される値
* @return 各ノードまでの最短距離のリスト
*/
std::vector<WEIGHT> distances(const std::vector<int> &start_nodes,
WEIGHT invalid) const {
std::vector<WEIGHT> dist(N, WEIGHT_MAX);
for (auto &x : start_nodes)
dist[x] = 0;
if constexpr (std::is_same<WEIGHT, int>::value) {
// BFS algorithm
std::queue<int> q;
for (auto &x : start_nodes)
q.push(x);
run_bfs(dist, q);
} else {
// Dijkstra's algorithm
Dijkstra_queue q;
std::set<int> st;
for (auto &x : start_nodes) {
q.push({0, x});
st.insert(uf.leader(x));
}
for (auto &x : st) {
reset_visited_flag(x);
}
run_Dijkstra(dist, q);
}
for (auto &x : dist)
if (x == WEIGHT_MAX)
x = invalid;
return dist;
}
matrix<WEIGHT> distances_from_all_nodes(WEIGHT invalid = -1) {
auto mt(to_adjajency(WEIGHT_MAX));
int N = mt.size_H();
for (int k = 0; k < N; k++) // 経由する頂点
for (int i = 0; i < N; i++) // 始点
for (int j = 0; j < N; j++) // 終点
if (mt(i, k) != WEIGHT_MAX && mt(k, j) != WEIGHT_MAX)
mt(i, j) = std::min(mt(i, j), mt(i, k) + mt(k, j));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (mt(i, j) == WEIGHT_MAX)
mt(i, j) = invalid;
return mt;
}
/**
* @brief 復元付き最短経路
* @attention 到達可能でないとき、空の配列で返る
*/
std::vector<edge<WEIGHT>> shortest_path(int start_node, int end_node) {
if (start_node == end_node)
return {};
auto dist = distances(start_node, WEIGHT_MAX);
if (dist[end_node] == WEIGHT_MAX)
return {};
auto R(this->reverse());
reset_visited_flag(end_node);
visited[end_node] = true;
int cu = end_node;
std::vector<edge<WEIGHT>> route;
while (cu != start_node) {
for (auto e : R[cu]) {
if (visited[e.to])
continue;
if (dist[cu] - e.cost == dist[e.to]) {
visited[cu = e.to] = true;
route.push_back(e.reverse());
break;
}
}
}
std::reverse(route.begin(), route.end());
return route;
}
WEIGHT diameter() const {
static_assert(!is_directed);
assert(is_tree());
std::vector<WEIGHT> dist(distances(0, -1));
dist = distances(
std::max_element(dist.begin(), dist.end()) - dist.begin(), -1);
return *std::max_element(dist.begin(), dist.end());
}
graph reverse() const {
if constexpr (!is_directed) {
return *this;
} else {
graph ret(N);
for (auto &e : E) {
ret.add_edge(e.reverse());
}
return ret;
}
}
std::vector<int> topological_sort() {
static_assert(is_directed);
std::vector<int> indeg(N, 0), sorted;
for (int to : E)
indeg[to]++;
std::queue<int> q;
for (int i = 0; i < N; i++)
if (!indeg[i])
q.push(i);
while (!q.empty()) {
int cu = q.front();
q.pop();
for (int to : G[cu]) {
if (!--indeg[to])
q.push(to);
}
sorted.push_back(cu);
}
return sorted;
}
/**
* @return 最小全域森
*/
graph minimum_spanning_forest() const {
static_assert(!is_directed);
graph ret(N);
std::vector<edge<WEIGHT>> tmp(edges());
std::sort(tmp.begin(), tmp.end());
for (auto &e : tmp)
if (!ret.are_connected(e.from, e.to))
ret.add_edge(e);
return ret;
}
private:
/**
* @see https://ei1333.github.io/luzhiled/snippets/graph/lowlink.html
* @attention 非連結でも動作
*/
int run_lowlink(int idx, int k, int par, std::vector<int> &ord,
std::vector<int> &low, std::vector<edge<WEIGHT>> &brds,
std::vector<int> &apts) {
visited[idx] = true;
ord[idx] = k++;
low[idx] = ord[idx];
bool is_apt = false;
int cnt = 0;
for (auto &e : G[idx]) {
if (!visited[e.to]) {
++cnt;
k = run_lowlink(e.to, k, idx, ord, low, brds, apts);
low[idx] = std::min(low[idx], low[e.to]);
is_apt |= ~par && low[e.to] >= ord[idx];
if (ord[idx] < low[e.to]) {
brds.emplace_back(e.minmax());
}
} else if (e.to != par) {
low[idx] = std::min(low[idx], ord[e.to]);
}
}
is_apt |= par == -1 && cnt > 1;
if (is_apt)
apts.push_back(idx);
return k;
}
public:
std::pair<std::vector<edge<WEIGHT>>, std::vector<int>> lowlink() {
static_assert(!is_directed);
std::vector<edge<WEIGHT>> brds;
std::vector<int> apts, ord(N, 0), low(N, 0);
reset_visited_flag();
int k = 0;
for (int i = 0; i < N; i++) {
if (!visited[i])
k = run_lowlink(i, k, -1, ord, low, brds, apts);
}
return {brds, apts};
}
void print() const {
std::cout << this->N << " " << this->E.size() << std::endl;
for (const edge<WEIGHT> &e : this->E)
std::cout << e << std::endl;
}
};
#line 5 "library/gandalfr/standard/mod_integer.hpp"
inline long long mod_inverse(long long a, int mod) {
assert(mod > 0);
long long b = mod, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b, std::swap(a, b);
u -= t * v, std::swap(u, v);
}
u %= mod;
if (u < 0)
u += mod;
return u;
}
// mod_integer<P> a := Pを法とするときの整数型;
template <int mod> class mod_integer {
private:
long long val; // 値は必ず 0 <= val < mod に保たれる
friend mod_integer operator+(const mod_integer &a) { return a; }
friend mod_integer operator-(const mod_integer &a) { return -a.val; }
friend mod_integer operator+(const mod_integer &a, const mod_integer &b) {
return mod_integer(a.val + b.val);
}
friend mod_integer operator-(const mod_integer &a, const mod_integer &b) {
return mod_integer(a.val - b.val);
}
friend mod_integer operator*(const mod_integer &a, const mod_integer &b) {
return mod_integer(a.val * b.val);
}
friend mod_integer operator/(const mod_integer &a, const mod_integer &b) {
return mod_integer((a.val * mod_inverse(b.val, mod)) % mod);
}
friend bool operator==(const mod_integer &a, const mod_integer &b) {
return a.val == b.val;
}
friend bool operator!=(const mod_integer &a, const mod_integer &b) {
return a.val != b.val;
}
// map とかに乗せたいので、便宜的に定義
friend bool operator<(const mod_integer &a, const mod_integer &b) {
return a.val < b.val;
}
public:
mod_integer(long long n) : val(n) {
val %= mod;
if (val < 0)
val += mod;
}
mod_integer() : val(0) {}
int value() const { return (int)val; }
mod_integer &operator=(const mod_integer &a) = default;
mod_integer &operator+=(const mod_integer &a) {
val += a.val;
if (val >= mod)
val -= mod;
return *this;
}
mod_integer &operator-=(const mod_integer &a) {
val -= a.val;
if (val < 0)
val += mod;
return *this;
}
mod_integer &operator*=(const mod_integer &a) {
(val *= a.val) %= mod;
return *this;
}
mod_integer &operator/=(const mod_integer &a) {
(val *= mod_inverse(a.val, mod)) %= mod;
return *this;
}
friend std::istream &operator>>(std::istream &is, mod_integer &a) {
is >> a.val;
a.val %= mod;
if (a.val < 0)
a.val += mod;
return is;
}
friend std::ostream &operator<<(std::ostream &os, const mod_integer &a) {
os << a.val;
return os;
}
};
// d_mod_integer<P> a := Pを法とするときの整数型;
template <int id> class dynamic_mod_integer {
private:
using d_mod_integer = dynamic_mod_integer<id>;
static inline int mod = 998244353;
long long val; // 値は必ず 0 <= val < mod に保たれる
friend d_mod_integer operator+(const d_mod_integer &a) { return a; }
friend d_mod_integer operator-(const d_mod_integer &a) { return -a.val; }
friend d_mod_integer operator+(const d_mod_integer &a,
const d_mod_integer &b) {
return d_mod_integer(a.val + b.val);
}
friend d_mod_integer operator-(const d_mod_integer &a,
const d_mod_integer &b) {
return d_mod_integer(a.val - b.val);
}
friend d_mod_integer operator*(const d_mod_integer &a,
const d_mod_integer &b) {
return d_mod_integer(a.val * b.val);
}
friend d_mod_integer operator/(const d_mod_integer &a,
const d_mod_integer &b) {
return d_mod_integer((a.val * mod_inverse(b.val, mod)) % mod);
}
friend bool operator==(const d_mod_integer &a, const d_mod_integer &b) {
return a.val == b.val;
}
friend bool operator!=(const d_mod_integer &a, const d_mod_integer &b) {
return a.val != b.val;
}
// map とかに乗せたいので、便宜的に定義
friend bool operator<(const d_mod_integer &a, const d_mod_integer &b) {
return a.val < b.val;
}
public:
dynamic_mod_integer(long long n) : val(n) {
val %= mod;
if (val < 0)
val += mod;
}
dynamic_mod_integer() : val(0) {}
int value() const { return (int)val; }
static void set_mod(int _mod) {
assert(_mod >= 0);
mod = _mod;
}
d_mod_integer &operator=(const d_mod_integer &a) = default;
d_mod_integer &operator+=(const d_mod_integer &a) {
val += a.val;
if (val >= mod)
val -= mod;
return *this;
}
d_mod_integer &operator-=(const d_mod_integer &a) {
val -= a.val;
if (val < 0)
val += mod;
return *this;
}
d_mod_integer &operator*=(const d_mod_integer &a) {
(val *= a.val) %= mod;
return *this;
}
d_mod_integer &operator/=(const d_mod_integer &a) {
(val *= mod_inverse(a.val, mod)) %= mod;
return *this;
}
friend std::istream &operator>>(std::istream &is, d_mod_integer &a) {
is >> a.val;
a.val %= mod;
if (a.val < 0)
a.val += mod;
return is;
}
friend std::ostream &operator<<(std::ostream &os, const d_mod_integer &a) {
os << a.val;
return os;
}
};
using mint = mod_integer<1000000007>;
using _mint = mod_integer<998244353>;
using dmint = dynamic_mod_integer<-1>;
#line 4 "library/gandalfr/math/prime_number_utility.hpp"
#line 6 "library/gandalfr/math/prime_number_utility.hpp"
#line 6 "library/gandalfr/math/enumeration_utility.hpp"
#line 8 "library/gandalfr/math/enumeration_utility.hpp"
template <class T> T power(T x, long long n) {
T ret = static_cast<T>(1);
while (n > 0) {
if (n & 1)
ret = ret * x;
x = x * x;
n >>= 1;
}
return ret;
}
long long power(long long x, long long n) {
long long ret = 1;
while (n > 0) {
if (n & 1)
ret = ret * x;
x = x * x;
n >>= 1;
}
return ret;
}
long long power(long long x, long long n, int MOD) {
long long ret = 1;
x %= MOD;
while (n > 0) {
if (n & 1)
ret = ret * x % MOD;
x = x * x % MOD;
n >>= 1;
}
return ret;
}
long long power(long long x, long long n, long long MOD) {
long long ret = 1;
x %= MOD;
while (n > 0) {
if (n & 1)
ret = (__int128_t)ret * x % MOD;
x = (__int128_t)x * x % MOD;
n >>= 1;
}
return ret;
}
template <class T> class factorial {
private:
static inline std::vector<T> fact{T(1)};
public:
factorial() = delete;
~factorial() = delete;
static T get(int n) {
while (n >= fact.size())
fact.push_back(fact.back() * fact.size());
return fact[n];
}
};
mint (*fact)(int) = factorial<mint>::get;
_mint (*_fact)(int) = factorial<_mint>::get;
template <class T> T permutation(int n, int k) {
assert(0 <= k && k <= n);
return factorial<T>::get(n) / factorial<T>::get(n - k);
}
mint (*perm)(int, int) = permutation<mint>;
_mint (*_perm)(int, int) = permutation<_mint>;
template <class T> static T combnation(int n, int k) {
assert(0 <= k && k <= n);
return factorial<T>::get(n) /
(factorial<T>::get(k) * factorial<T>::get(n - k));
}
mint (*comb)(int, int) = combnation<mint>;
_mint (*_comb)(int, int) = combnation<_mint>;
#line 8 "library/gandalfr/math/prime_number_utility.hpp"
/**
* @see https://drken1215.hatenablog.com/entry/2023/05/23/233000
*/
bool MillerRabin(long long N, const std::vector<long long> &A) {
long long s = 0, d = N - 1;
while (d % 2 == 0) {
++s;
d >>= 1;
}
for (auto a : A) {
if (N <= a)
return true;
long long t, x = power(a, d, N);
if (x != 1) {
for (t = 0; t < s; ++t) {
if (x == N - 1)
break;
x = (__int128_t)x * x % N;
}
if (t == s)
return false;
}
}
return true;
}
/**
* @brief 素数判定や列挙をサポートするクラス
* @brief 素数篩を固定サイズで構築、それをもとに素数列挙などを行う
*/
class Eratosthenes {
protected:
static inline int seive_size = (1 << 24);
static inline std::vector<bool> sieve;
static inline std::vector<int> primes{2, 3}, movius, min_factor;
static void make_table() {
sieve.assign(seive_size, true);
sieve[0] = sieve[1] = false;
movius.assign(seive_size, 1);
min_factor.assign(seive_size, 1);
for (int i = 2; i <= seive_size; ++i) {
if (!sieve[i])
continue;
movius[i] = -1;
min_factor[i] = i;
primes.push_back(i);
for (int j = i * 2; j < seive_size; j += i) {
sieve[j] = false;
movius[j] = ((j / i) % i == 0 ? 0 : -movius[j]);
if (min_factor[j] == 1)
min_factor[j] = i;
}
}
}
static std::vector<std::pair<long long, int>> fast_factorize(long long n) {
std::vector<std::pair<long long, int>> ret;
while (n > 1) {
if (ret.empty() || ret.back().first != min_factor[n]) {
ret.push_back({min_factor[n], 1});
} else {
ret.back().second++;
}
n /= min_factor[n];
}
return ret;
}
static std::vector<std::pair<long long, int>> naive_factorize(long long n) {
std::vector<std::pair<long long, int>> ret;
for (long long p : primes) {
if (n == 1 || p * p > n)
break;
while (n % p == 0) {
if (ret.empty() || ret.back().first != p)
ret.push_back({p, 1});
else
ret.back().second++;
n /= p;
}
}
if (n != 1)
ret.push_back({n, 1});
return ret;
}
public:
Eratosthenes() = delete;
~Eratosthenes() = delete;
static void set_init_size(int size) {
assert(sieve.empty());
seive_size = size;
}
/**
* @brief n が素数かを判定
* @attention if n < (1 << 24) : O(1)
* @attention else : O(log(N))
*/
static bool is_prime(long long n) {
if (sieve.empty())
make_table();
assert(1 <= n);
if (n > 2 && (n & 1LL) == 0) {
return false;
} else if (n < seive_size) {
return sieve[n];
} else if (n < 4759123141LL) {
return MillerRabin(n, {2, 7, 61});
} else {
return MillerRabin(
n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}
}
/**
* @brief 素因数分解する
* @return factorize(p1^e1 * p2^e2 * ...) => {{p1, e1}, {p2, e2], ...},
* @return factorize(1) => {}
* @attention if n < (1 << 24) : O(log(N))
* @attention if n < (1 << 24) : O(N^(3/2))
*/
static std::vector<std::pair<long long, int>> factorize(long long n) {
if (sieve.empty())
make_table();
assert(1 <= n);
if (n < seive_size) {
return fast_factorize(n);
} else {
return naive_factorize(n);
}
}
static int Movius(int n) {
if (movius.empty())
make_table();
assert(1 <= n);
return movius.at(n);
}
/**
* @brief オイラーのトーシェント関数
*/
long long totient(long long n) {
long long ret = 1;
for (auto [b, e] : factorize(n))
ret *= power(b, e - 1) * (b - 1);
return ret;
}
static int kth_prime(int k) { return primes.at(k); }
};
#line 6 "playspace/main.cpp"
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MAXINT = std::numeric_limits<int>::max();
const int MININT = std::numeric_limits<int>::min();
const ll INFLL = 1001001001001001001;
const ll MAXLL = std::numeric_limits<ll>::max();
const ll MINLL = std::numeric_limits<ll>::min();
const ll MOD = 1000000007;
const ll _MOD = 998244353;
#define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++)
#define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--)
#define all(a) (a).begin(),(a).end()
#define LF cout << endl
#ifdef ENABLE_MULTI_FOR
#define mrep(it, mr) for(multi_iter it(mr); !it.fin(); ++it)
#endif
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
void Yes(bool ok){ std::cout << (ok ? "Yes" : "No") << std::endl; }
int main(void){
Eratosthenes::set_init_size(1000001);
int N, M;
cin >> N >> M;
vector<int> ord(N);
iota(all(ord), 0);
rep(i,0,M) {
int c;
cin >> c;
vector<int> A(c);
cin >> A;
rep(j,0,c) A[j]--;
int keep = ord[A[0]];
rrep(j,0,c) {
ord[A[(j+1)%c]] = ord[A[j]];
}
ord[A[1]] = keep;
}
graph<int, false> G(N);
rep(i,0,N) {
G.add_edge(i, ord[i]);
}
auto cc = G.weakly_connected_components();
map<int, int> L;
rep(i,0,cc.size()) {
auto fs = Eratosthenes::factorize(cc[i].size());
for (auto [b, e]: fs) {
chmax(L[b], e);
}
}
_mint ans = 1;
for (auto [b, e] : L) ans *= power<_mint>(b, e);
cout << ans << endl;
}