Erase Nodes
시간 제한7초메모리 제한512 MB
노드 n개와 간선 n개로 이루어진 연결 그래프에서 활성 노드를 무작위로 하나씩 지울 때, BFS 갱신 횟수의 기댓값을 998244353으로 나눈 나머지로 구한다.
문제
Bob’s job is to maintain a network, which can be represented as a connected graph having n nodes and n undirected edges, but now he has to close the entire network.
In the beginning, all nodes are active. During the processing of closing, he will repeatedly select one active node and inactivate it until there is no active node. However, each active node has a table that stores the connectivity information from this node to any other active node. When a node u is inactivated, every active node v (including u itself) that used to be able to reach u have to update its own table. Each update may change several records, as each inactivation can cut a connected component into several smaller components, but the cost of each update is almost the same — running a breadth-first search from v.
Now Bob is wondering in which order he should close these nodes because he knows if he operated these nodes in a bad order, the number of updates would be a bit large. He is not good at finding a good solution, so he chooses to randomly select one active node with equal probability at any time. Could you help him estimate the expected number of updates?
To avoid any precision issue, if the answer can be represented as an irreducible fraction p/q, then you are asked to report the minimum non-negative integer r such that qr ≡ p (mod 998244353). For example, 6 × 166374072 ≡ 79, 3 × 332748131 ≡ 40 (mod 998244353).
입력
The input contains several test cases. The first line contains an integer T indicating the number of test cases. The following describes all test cases. For each test case:
The first line contains 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” (without quotes), where x is the test case number starting from 1, and y is the answer to this test case.
제한
- 1 ≤ T ≤ 100
- 3 ≤ n ≤ 105
- 1 ≤ u < v ≤ n
- The sum of n in all test cases does not exceed 5 × 105.
- It is guaranteed that edges for each test case are distinct, which means there are no multiple edges.