#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, p = 998244353;
int Case, n, fk[N];
bool vis[N];
int tot, fi[N], a[N << 1], ne[N << 1];
inline void A(int &x, int y) { x = (x + y >= p ? x + y - p : x + y); }
inline int Qpow(int x, int y = p - 2) {
	int ans = 1;
	for (; y; y >>= 1, x = 1ll * x * x % p) 
		if (y & 1) ans = 1ll * ans * x % p;
	return ans;
}
inline void Add(int x, int y) {
	a[++tot] = y; ne[tot] = fi[x]; fi[x] = tot;
}
namespace DSU {
	int fa[N];
	inline void Init() {
		memset(fa + 1, 0, n * sizeof *fa);
	}
	inline int Ask(int x) {
		return fa[x] ? fa[x] = Ask(fa[x]) : x;
	}
	inline bool Merge(int x, int y) {
		x = Ask(x); y = Ask(y);
		if (x == y) return 0;
		fa[x] = y;
		return 1;
	}
}
namespace CircleTree {
	inline void Solve(int x) {
		
	}
}
namespace Tree {
	int f[N][2], pl[N][2];
	inline void Update(int &x, int &pl1, int y, int pl2) {
		if (y < x) { x = y; pl1 = pl2; }
		else if (x == y) { A(pl1, pl2); }
	}
	inline void Dfs(int x, int fa) {
		f[x][0] = 0; pl[x][0] = 1;
		for (int i = fi[x]; i; i = ne[i]) if (a[i] != fa) {
			Dfs(a[i], x);
			f[x][0] += f[a[i]][0] + (i & 1);
			pl[x][0] = 1ll * pl[x][0] * pl[a[i]][0] % p;
		}
		f[x][1] = f[x][0]; pl[x][1] = pl[x][0];
		for (int i = fi[x]; i; i = ne[i]) if (a[i] != fa) {
			Update(f[x][1], pl[x][1], f[x][0] + (i & 1 ? -1 : 1), 1ll * pl[x][0] * Qpow(pl[a[i]][0]) % p * pl[i][1] % p);
		}
	}
	inline void Solve(int x) {
		Dfs(x, 0);
	}
}
int main() {
	scanf("%d", &Case);
	while (Case--) {
		scanf("%d", &n);
		tot = 1; memset(fi + 1, 0, n * sizeof *fi);
		memset(fk + 1, 0, n * sizeof *fk);
		memset(vis + 1, 0, n * sizeof vis);
		for (int i = 1, x, y; i <= n; ++i) {
			scanf("%d%d", &x, &y);
			Add(x, y); Add(y, x);
			if (!DSU::Merge(x, y)) ++fk[x];
		}
		for (int i = 1; i <= n; ++i) if (fk[i]) {
			int u = DSU::Ask(i);
			if (u != i) fk[u] += fk[i];
		}
		bool no_answer = 0;
		for (int i = 1; i <= n; ++i) if (fk[DSU::Ask(i)] >= 2) no_answer = 1;
		if (no_answer) { puts("-1 -1"); continue; } 
		int ans = 0, plan = 1;
		for (int i = 1; i <= n; ++i) if (!vis[i]) {
			if (fk[DSU::Ask(i)] == 1) {
				CircleTree::Solve(i);
			} else {
				Tree::Solve(i);
				printf("%d %d\n", Tree::f[i][0], Tree::pl[i][0]);
				ans += Tree::f[i][0];
				plan = 1ll * plan * Tree::pl[i][0] % p;
			}
		}
		printf("%d %d\n", ans, plan);
	}
	return 0;
}