#include <bits/stdc++.h>
#define coutarr(x) for (auto it : x) cout << it << " ";cout << '\n';
using namespace std;
#define int long long
constexpr int MOD = 998244353;
int fpow(int base, int pow) {
	int rval = 1;
	while (pow) {
		if (pow & 1) {
			rval = (rval * base) % MOD;
		}
		pow >>= 1;
		base = (base * base) % MOD;
	}
	return rval;
}
void chmin(int &a, int b){
	if (b < a) a = b;
}
struct DSU{
	vector<int> par;
	DSU(int n) {
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int find(int node) {
		if (par[node] == node) return node;
		return par[node] = find(par[node]);
	}
	void merge(int a, int b) {
		par[find(a)] = b;
	}
};
int no_of_unique(vector<int> a) {
	sort(a.begin(), a.end());
	return unique(a.begin(), a.end())-a.begin();
}
vector<int> separate(vector<vector<int>> graph) {
	int n = graph.size();
	vector<int> dept(n, -1);
	vector<int> par(n);
	DSU dsu(n);
	function<int(int,int)> dfs = [&](int node, int lnode)->int{
		par[node] = lnode;
		int mi_dept = dept[node];
		int sy = 0;
		for (auto it : graph[node]) {
			if (it != lnode) {
				if (dept[it] == -1) {
					dept[it] = dept[node] + 1;
					chmin(mi_dept, dfs(it, node));
				} else chmin(mi_dept, dept[it]);
			} else sy++;
		}
		if (sy == 2) chmin(mi_dept, dept[lnode]);
		if (mi_dept < dept[node]) {
			dsu.merge(node, lnode);
		}
		return mi_dept;
	};
	dept[0] = 0;
	dfs(0, -1);
	vector<int> ret(n);
	vector<int> compres;
	for (int i = 0; i < n; ++i)
	{
		ret[i] = dsu.find(i);
		compres.push_back(ret[i]);
	}
	sort(compres.begin(), compres.end());
	compres.erase(unique(compres.begin(), compres.end()), compres.end());
	for (int i = 0; i < n; ++i)
	{
		ret[i] = lower_bound(compres.begin(), compres.end(), ret[i]) - compres.begin();
	}
	return ret;
}
int SUMN=0,SUMM=0;
bool isconnected(int N, std::vector<int32_t> U, std::vector<int32_t> V) {
	std::vector<bool> vis(N);
	std::vector<int> stk;
	stk.push_back(0);
	std::vector<std::vector<int>> arr(N);
	for (int i = 0; i < U.size(); ++i)
	{
		arr[U[i]-1].push_back(V[i]-1);
		arr[V[i]-1].push_back(U[i]-1);
	}
	while (stk.size()) {
		int node = stk.back();
		stk.pop_back();
		if (vis[node]) continue;
		vis[node] = true;
		for (auto it : arr[node]) {
			stk.push_back(it);
		}
	}
	for (int i = 0; i < N; ++i)
	{
		if (!vis[i]) return false;
	}
	return true;
}
std::vector<int32_t> toplanti(int32_t N, int32_t M, std::vector<int32_t> C, std::vector<int32_t> U, std::vector<int32_t> V) {
	assert(isconnected(N,U,V));
	SUMN+=N,SUMM+=M;for(auto it:C)assert(it>=0 && it<=1000000000);for(int i = 0; i < M; i++)assert(U[i]!=V[i]&&U[i]>=1&&U[i]<=N&&V[i]>=1&&V[i]<=N);assert(SUMN<=200000&&SUMM<=300000);
	int n = N, m = M;
	vector<int> c(n);
	int somma = 0;
	for (int i = 0; i < n; ++i) {
		c[i] = C[i];
		somma += c[i];
		if (somma >= MOD) somma -= MOD;
	}
	vector<vector<int>> arr(n);
	for (int i = 0; i < m; ++i) {
		arr[U[i]-1].push_back(V[i]-1);
		arr[V[i]-1].push_back(U[i]-1);
	}
	auto groups = separate(arr);
	int N_Q = no_of_unique(groups);
	vector<vector<int>> groups_tree(N_Q);
	vector<int> gC(N_Q), gSum(N_Q);
	for (int i = 0; i < n; i++) {
		gC[groups[i]] += c[i];
		if (gC[groups[i]] >= MOD) gC[groups[i]] -= MOD;
		gSum[groups[i]]++;
		if (gSum[groups[i]] >= MOD) gSum[groups[i]] -= MOD;
		for (auto j : arr[i]) {
			if (groups[i] != groups[j]) {
				groups_tree[groups[i]].push_back(groups[j]);
			}
		}
	}
	function<void(int,int)> dfs = [&](int node, int lnode)->void{
		for (auto it : groups_tree[node]) if (it != lnode) {
			dfs(it, node);
			gC[node] += gC[it];
			gSum[node] += gSum[it];
			if (gC[node] >= MOD) gC[node] -= MOD;
			if (gC[node] < 0) gC[node] += MOD;
		}
	};
	dfs(0, -1);

	vector<int> a = c, b(n);
	for (int i = 0; i < n; i++) {
		for (auto j : arr[i]) if (groups[i] != groups[j]) {
			if (gSum[groups[i]] > gSum[groups[j]]) {
				a[i] += gC[groups[j]];
				b[i] += gSum[groups[j]];
			}
			else {
				a[i] += (somma - gC[groups[i]])%MOD;
				b[i] += (n - gSum[groups[i]])%MOD;
			}
			if (a[i] >= MOD) a[i] -= MOD;
			if (a[i] < 0) a[i] += MOD;
			if (b[i] >= MOD) b[i] -= MOD;
			if (b[i] < 0) b[i] += MOD;
		}
	}
	vector<vector<int>> cycles(N_Q);
	vector<bool> vis(n, false);
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		int node = i;
		int g = groups[node];
		while (!vis[node]) {
			cycles[g].push_back(node);
			vis[node] = true;
			for (auto it : arr[node]) if (groups[it] == g && !vis[it]) {
				node = it;
				break;
			}
		}
	}
	int ans1 = 1;
	int ans2 = 0;
	for (auto &g : cycles) {
		ans1 = (ans1 * g.size()) % MOD;
	}
	for (auto g : cycles) {
		int group_ans = 0;
		int gsz = g.size();
		int outside = (ans1 * fpow(gsz, MOD - 2))%MOD;
		int t_agi = 0;
		int t_bgi = 0;
		for (int i = 0; i < gsz; i++) {
			group_ans -= (((gsz * a[g[i]])%MOD) * b[g[i]])%MOD;
			if (group_ans < 0) group_ans += MOD;
			t_agi += a[g[i]];
			t_bgi += b[g[i]];
			if (t_agi >= MOD) t_agi -= MOD;
			if (t_bgi >= MOD) t_bgi -= MOD;
		}
		group_ans += (((gsz * t_agi)%MOD)*t_bgi)%MOD;
		if (group_ans >= MOD) group_ans -= MOD;

		array<int,3> cons = array<int,3>();
		for (int i = 0; i < gsz; i++) {
			array<int,3> cons2 = {
				(a[g[i]] * i) % MOD,
				(a[g[i]] * ((i * gsz - i * i) % MOD))%MOD,
				a[g[i]]
			};
			for (int j = 0; j < 3; ++j)
			{
				group_ans += (2 * cons[j] * cons2[j])%MOD;
				if (group_ans >= MOD) group_ans -= MOD;
				if (group_ans < 0) group_ans += MOD;
			}
			cons[0] += (2 * i * (b[g[i]] + 1)) % MOD;
			cons[1] += (b[g[i]] + 1)%MOD;
			cons[2] += (((i * i + i * gsz)%MOD) * (-b[g[i]] - 1))%MOD;

			for (int j = 0; j < 3; ++j) {
				if (cons[j] >= MOD) cons[j] -= MOD;
				if (cons[j] < 0) cons[j] += MOD;
			}
		}

		cons = array<int,3>();
		for (int i = gsz - 1; i >= 0; i--) {
			array<int,3> cons2 = {
				(a[g[i]] * i) % MOD,
				(-a[g[i]] * ((i * i + gsz * i) % MOD))%MOD,
				a[g[i]]
			};
			for (int j = 0; j < 3; ++j) {
				group_ans += (2 * cons[j] * cons2[j])%MOD;
				if (group_ans >= MOD) group_ans -= MOD;
				if (group_ans < 0) group_ans += MOD;
			}
			cons[0] += (2 * i * (b[g[i]] + 1))%MOD;
			cons[1] += (b[g[i]] + 1)%MOD;
			cons[2] += (((gsz * i - i * i)%MOD) * (b[g[i]] + 1))%MOD;
			for (int j = 0; j < 3; ++j) {
				if (cons[j] >= MOD) cons[j] -= MOD;
				if (cons[j] < 0) cons[j] += MOD;
			}
		}
		ans2 += (group_ans * outside)%MOD;
		if (ans2 < 0) ans2 += MOD;
		if (ans2 >= MOD) ans2 -= MOD;
	}
	for (int i = 0; i < n; i++) {
		int cur_ans = 0;
		int pref_a = c[i];
		int pref_b = 0;
		for (auto j : arr[i]) if (groups[i] != groups[j]) {
			int cA, cB;
			if (gSum[groups[i]] > gSum[groups[j]]) {
				cA = gC[groups[j]];
				cB = gSum[groups[j]];
			}
			else {
				cA = somma - gC[groups[i]];
				if (cA < 0) cA += MOD;
				cB = n - gSum[groups[i]];
			}
			cur_ans += (pref_a * cB)%MOD;
			if (cur_ans >= MOD) cur_ans -= MOD;
			cur_ans += (pref_b * cA)%MOD;
			if (cur_ans >= MOD) cur_ans -= MOD;
			pref_a += cA;
			pref_b += cB;
			if (pref_a >= MOD) pref_a -= MOD;
			if (pref_b >= MOD) pref_b -= MOD;
		}
		ans2 += (cur_ans * ans1)%MOD;
		if (ans2 >= MOD) ans2 -= MOD;
	}
	ans1 *= n;
	ans1 %= MOD;
	vector<int32_t> ret;
	ret.push_back(ans1);
	ret.push_back(ans2);
	return ret;
}
