// -------------------- main code begins at #263 -------------------- // #include using namespace std; template using vp = vector>; template using pque = priority_queue; template using lpque = priority_queue, greater>; template using umap = unordered_map; template using uset = unordered_set; #define pque_op(T, op) (priority_queue, decltype(op)>(op)) #define set_op(T, op, ...) (set(__VA_OPT__(__VA_ARGS__, ) op)) using lint = long long; using pint = pair; using plint = pair; using pil = pair; using pli = pair; using vint = vector; using vlint = vector; using vpint = vector; using vplint = vector; using vpil = vector; using vpli = vector; using vbl = vector; using qint = queue; using qlint = queue; constexpr double PI = 3.141592653589793; constexpr int INTINF = (1 << 30) - 1; constexpr lint LLINF = (1LL << 62) - 1; constexpr int MPRIME = 1000000007; constexpr int MPRIME9 = 998244353; constexpr lint MMPRIME = (1LL << 61) - 1; constexpr char newl = '\n'; #define len length() #define empb(...) emplace_back(__VA_ARGS__) #define fi first #define se second #define get_rep(_1, _2, _3, func, ...) func #define rep(i, ...) get_rep(__VA_ARGS__, rep3, rep2, rep1)(i, __VA_ARGS__) #define rep1(i, N) for(int i = 0; i < (N); i++) #define rep2(i, s, t) for(int i = (s); i < (t); i++) #define rep3(i, s, t, a) for(int i = (s); i < (t); i += (a)) #define get_rrep(_1, _2, _3, func, ...) func #define rrep(i, ...) get_rrep(__VA_ARGS__, rrep3, rrep2, rrep1)(i, __VA_ARGS__) #define rrep1(i, N) for(int i = (N); i >= 0; i--) #define rrep2(i, s, t) for(int i = (s); i >= (t); i--) #define rrep3(i, s, t, a) for(int i = (s); i >= (t); i -= (a)) #define forbit(bit, k) for(int bit = 0; bit < (1 << (k)); bit++) #define forsubset(bit, orig_bit) \ for(int bit = (orig_bit), _cnt = 0; (_cnt += (bit == (orig_bit))) < 2; --bit &= (orig_bit)) #define bitpop(bit, k) (((bit) >> (k)) & 1) #define all(name) name.begin(), name.end() #define rall(name) name.rbegin(), name.rend() #define gsort(vbeg, vend) sort(vbeg, vend, greater<>()) #define dbg(x) cerr << #x << ": " << x << '\n'; inline int popcnt(lint bit) { return __builtin_popcountll(bit); } template inline bool chmin(T &a, T b) { if(a > b) { a = b; return true; } return false; } template inline bool chmax(T &a, T b) { if(a < b) { a = b; return true; } return false; } template inline void init(vector &v) { for(auto &a : v) cin >> a; } template inline void init(vector> &v) { for(auto &a : v) cin >> a.first >> a.second; } template inline void init(vector &v, int n) { v.resize(n); for(auto &a : v) cin >> a; } template inline void init(vector &v1, vector &v2, int n) { v1.resize(n); v2.resize(n); for(int i = 0; i < n; i++) cin >> v1[i] >> v2[i]; } template inline void init(vector &v1, vector &v2, vector &v3, int n) { v1.resize(n); v2.resize(n); v3.resize(n); for(int i = 0; i < n; i++) cin >> v1[i] >> v2[i] >> v3[i]; } template inline void init(vector> &v, int n) { v.resize(n); for(auto &a : v) cin >> a.first >> a.second; } template inline void init(vector &v, int n, const T &c) { v.resize(n); for(auto &a : v) { cin >> a; a += c; } } template inline void init(vector &v1, vector &v2, int n, const T1 &c1, const T2 &c2) { v1.resize(n); v2.resize(n); for(int i = 0; i < n; i++) { cin >> v1[i] >> v2[i]; v1[i] += c1; v2[i] += c2; } } template inline void init(vector &v1, vector &v2, vector &v3, int n, const T1 &c1, const T2 &c2, const T3 &c3) { v1.resize(n); v2.resize(n); v3.resize(n); for(int i = 0; i < n; i++) { cin >> v1[i] >> v2[i] >> v3[i]; v1[i] += c1; v2[i] += c2; v3[i] += c3; } } template inline void init(vector> &v, int n, T &c1, U &c2) { v.resize(n); for(auto &a : v) { cin >> a.first >> a.second; a.first += c1; a.second += c2; } } inline void out() { cout << newl; } template inline void out(T a) { cout << a << '\n'; } template inline void out(T a, U... lst) { cout << a << " "; out(forward(lst)...); } template inline void out(vector &v) { for(int i = 0; i < v.size(); i++) cout << v[i] << (i == v.size() - 1 ? '\n' : ' '); cout << flush; } template void resiz(N n) {} template void resiz(N n, T &&hd, U &&...tl) { hd.resize(n); resiz(n, forward(tl)...); } bool Yes(bool b = true) { cout << (b ? "Yes" : "No") << newl; return b; } bool YES(bool b = true) { cout << (b ? "YES" : "NO") << newl; return b; } bool No(bool b = true) { if(!b) return false; cout << "No" << newl; return true; } bool NO(bool b = true) { if(!b) return false; cout << "NO" << newl; return true; } template struct v2d { private: vector> m; public: v2d() {} v2d(int h, int w) : m(h, vector(w)) {} v2d(int h, int w, const T &init) : m(h, vector(w, init)) {} v2d(const initializer_list> m_init) : m(m_init.begin(), m_init.end()) {} void assign(int h, int w) { m.assign(h, vector(w)); } void assign(int h, int w, const T init) { m.assign(h, vector(w, init)); } inline int size() const { return m.size(); } void in() { for(vector &v : m) for(T &val : v) cin >> val; } void in(int h, int w) { m.resize(h, vector(w)); in(); } void out() { int h = m.size(); for(vector &v : m) { int sz = v.size(); for(int j = 0; j < sz; j++) { cout << v[j] << (j == sz - 1 ? '\n' : ' '); } } cout << flush; } inline vector &operator[](int idx) { assert(0 <= idx && idx < int(m.size())); return m[idx]; } bool rangeout(int x, int y) { if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true; return false; } }; long long binpow(long long a, long long ex, long long p = MMPRIME) { long long res = 1; while(ex > 0) { if(ex & 1) (res *= a) %= p; ex >>= 1; (a *= a) %= p; } return res; } inline void init_e(v2d &E, int n, int m, int c) { E.assign(n, 0); int u, v; for(int i = 0; i < m; i++) { cin >> u >> v; u += c; v += c; E[u].emplace_back(v); E[v].emplace_back(u); } } // -------------------- main code -------------------- // template struct modint { private: long long val; public: modint(long long x = 0) : val((mod + x % mod) % mod) {} private: modint inv() const { long long x_ = val, xd = 1, xdd = 0, y_ = mod, yd = 0, ydd = 1, div; while(true) { if(!y_) return modint(xd); div = x_ / y_; x_ -= div * y_; xd -= div * yd; xdd -= div * ydd; if(!x_) return modint(yd); div = y_ / x_; y_ -= div * x_; yd -= div * xd; ydd -= div * xdd; } } public: modint operator-() const { return modint(-val); } modint &operator+=(const modint &a) { val += a.val; if(val >= mod) val -= mod; return *this; } modint &operator-=(const modint &a) { val -= a.val; if(val < 0) val += mod; return *this; } modint &operator*=(const modint &a) { (val *= a.val) %= mod; return *this; } modint &operator/=(const modint &a) { return (*this) *= a.inv(); } modint &operator+=(const long long &a) { (val += mod + a % mod) %= mod; return *this; } modint &operator-=(const long long &a) { (val += mod - a % mod) %= mod; return *this; } modint &operator*=(const long long &a) { (val *= mod + a % mod) %= mod; return *this; } modint &operator/=(const long long &a) { return (*this) /= modint(a); } modint operator+(const modint &a) const { return modint(*this) += a; } modint operator-(const modint &a) const { return modint(*this) -= a; } modint operator*(const modint &a) const { return modint(*this) *= a; } modint operator/(const modint &a) const { return modint(*this) /= a; } modint operator+(const long long &a) const { return modint(*this) += a; } modint operator-(const long long &a) const { return modint(*this) -= a; } modint operator*(const long long &a) const { return modint(*this) *= a; } modint operator/(const long long &a) const { return modint(*this) /= modint(a); } modint &operator++() { (++val) %= mod; return *this; } modint operator++(int) { modint res(*this); (++val) %= mod; return res; } modint &operator--() { (val += mod - 1) %= mod; return *this; } modint operator--(int) { modint res(*this); (val += mod - 1) %= mod; return res; } bool operator==(const modint &a) const { return val == a.val; } bool operator!=(const modint &a) const { return val != a.val; } bool operator<(const modint &a) const { return val < a.val; } bool operator>(const modint &a) const { return val > a.val; } bool operator<=(const modint &a) const { return val <= a.val; } bool operator>=(const modint &a) const { return val >= a.val; } bool operator==(const long long &a) const { return val == a; } bool operator!=(const long long &a) const { return val != a; } bool operator<(const long long &a) const { return val < a; } bool operator>(const long long &a) const { return val > a; } bool operator<=(const long long &a) const { return val <= a; } bool operator>=(const long long &a) const { return val >= a; } modint &operator=(const modint &a) { val = a.val; return *this; } modint &operator=(const long long &a) { val = (mod + a % mod) % mod; return *this; } friend ostream &operator<<(ostream &os, const modint &a) { return os << a.val; } friend istream &operator>>(istream &is, modint &a) { long long n; is >> n; a = modint(n); return is; } }; using mint = modint<998244353>; template struct UnionFind { private: vector parent; vector num; vector val; int treenum; const function swap_flg = [this](const int l, const int r, const T &, const T &) { return num[l] < num[r]; }; const function merge_val = [this](T &, const T &) {}; public: UnionFind(int n) : parent(n), num(n, 1), treenum(n) { for(int i = 0; i < n; i++) parent[i] = i; } UnionFind(int n, function f1) : parent(n), num(n, 1), val(n), treenum(n), swap_flg(f1) { for(int i = 0; i < n; i++) parent[i] = i; } UnionFind(int n, const function f2) : parent(n), num(n, 1), val(n), treenum(n), merge_val(f2) { for(int i = 0; i < n; i++) parent[i] = i; } UnionFind(int n, function f1, const function f2) : parent(n), num(n, 1), val(n), treenum(n), swap_flg(f1), merge_val(f2) { for(int i = 0; i < n; i++) parent[i] = i; } UnionFind(vector &v, const function f2) : parent(v.size()), num(v.size(), 1), val(v), treenum(v.size()), merge_val(f2) { for(int i = 0; i < v.size(); i++) parent[i] = i; } UnionFind(vector &v, function f1, const function f2) : parent(v.size()), num(v.size(), 1), val(v), treenum(v.size()), swap_flg(f1), merge_val(f2) { for(int i = 0; i < v.size(); i++) parent[i] = i; } int root(int x) { assert(x < parent.size()); if(parent[x] == x) return x; return parent[x] = root(parent[x]); } int size(int x) { assert(x < parent.size()); return num[root(x)]; } int merge(int x, int y) { assert(x < parent.size() && y < parent.size()); int xrt = root(x); int yrt = root(y); if(xrt == yrt) return xrt; if(swap_flg(xrt, yrt, val[xrt], val[yrt])) swap(xrt, yrt); parent[yrt] = xrt; num[xrt] += num[yrt]; merge_val(val[xrt], val[yrt]); treenum--; return xrt; } bool same(int x, int y) { assert(x < parent.size() && y < parent.size()); return root(x) == root(y); } int tnum() { return treenum; } inline T &operator[](int x) { assert(x < parent.size()); return val[x]; } }; int N, M; vector A; void input() { cin >> N >> M; init(A, N); } void solve() { auto mrg = [](mint &l, mint &r) { l += r; }; auto uf = UnionFind(A, mrg); for(int i = 0; i < M; i++) { int u, v; cin >> u >> v; u--, v--; uf.merge(u, v); } mint ans = 1; for(int i = 0; i < N; i++) { if(uf.root(i) == i) { rep(j, uf.size(i)) ans *= uf[i]; } } out(ans); } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); int t = 1; // cin >> t; while(t--) { input(); solve(); } }