1009. Six Grade

题目描述

现在是 2026 年 6 月的六级考试。

小 H 在考场考试，碰到了一种极其困难的题目：

这道题总共有 n 个题目与 n 个选项，这 n 个题目和 n 个选项是一一对应的（也就是每道题的答案都不一样）。

小 H 绞尽脑汁，最后终于把每道题确定在两个选项之内，也就是确保这个题目的标准答案在这两个选项之内。

小 H 没有办法了，他想找到一种策略，使得题目正确的期望最大。

输入格式

第一行一个整数 $T（1\le T\le 10）$，表示数据组数。

对于每组数据，第一行一个整数 $n（3\le n\le 10^6）$，表示题目数量。

接下来 $n$ 行，第 $i$ 行有两个不同的整数 $a_i, b_i（1\le a_i, b_i\le n）$，表示第 $i$ 道题可能的两个选项。

输出格式

对于每组数据，输出一个答案，表示这组数据回答正确题目的期望最大是多少。

答案对 998244353 取模。

样例输入

1
4
1 2
2 1
3 4
4 3

样例输出

2

提示

对于样例，最优策略之一是四道题依次选 1，2，3，4 ，此时正确题目数量的期望是 2。

来源：2026杭电多校-测试专用（四川大学） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1231&pid=1009