#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;
}