Erase Nodes

Bob's job is to maintain a network, which can be represented as a connected graph having $n$ nodes and $n$ undirected edges. Now he has to close the entire network.

In the beginning, all nodes are active. During the closing process, he repeatedly selects one active node and inactivates it until no active node remains. Each active node has a table that stores the connectivity information from that node to every other active node. When a node $u$ is inactivated, every active node $v$ (including $u$ itself) that could reach $u$ must update its table. Each update may change several records, since one inactivation can split a connected component into several smaller components, but the cost of each update is almost the same: running a breadth-first search from $v$.

A bad order makes the number of updates large. Bob does not know how to find a good order, so he selects one active node uniformly at random at each step. Find the expected number of updates.

To avoid precision issues, if the answer is an irreducible fraction $p/q$, report the minimum non-negative integer $r$ such that $q r \equiv p \pmod{998244353}$. For example, $6 \times 166374072 \equiv 79$ and $3 \times 332748131 \equiv 40 \pmod{998244353}$.

The input contains several test cases. The first line contains an integer $T$, the number of test cases. Each test case begins with an integer $n$. Each of the following $n$ lines contains two integers $u$ and $v$, representing an edge between the $u$-th node and the $v$-th node.

For each test case, output a line containing "Case #x: y", where $x$ is the test case number starting from 1, and $y$ is the answer to that test case.

• $1 \le T \le 100$
• $3 \le n \le 10^5$
• $1 \le u < v \le n$
• The sum of $n$ over all test cases does not exceed $5 \times 10^5$.
• The edges of each test case are distinct. There are no multiple edges.