노드 지우기

Bob의 일은 $n$개의 노드와 $n$개의 무방향 간선으로 이루어진 연결 그래프로 표현되는 네트워크를 관리하는 것이다. 이제 그는 네트워크 전체를 닫아야 한다.

처음에는 모든 노드가 활성 상태이다. 닫는 과정에서 그는 활성 노드를 하나씩 골라 비활성화하며, 활성 노드가 하나도 남지 않을 때까지 이를 반복한다. 각 활성 노드는 자신에서 다른 모든 활성 노드까지의 연결 정보를 저장한 표를 갖는다. 노드 $u$가 비활성화되면, $u$에 도달할 수 있었던 모든 활성 노드 $v$(자기 자신 $u$ 포함)는 자신의 표를 갱신해야 한다. 비활성화 한 번으로 연결 요소가 여러 개의 작은 연결 요소로 나뉠 수 있으므로 한 번의 갱신에서 여러 기록이 바뀔 수 있다. 다만 갱신 한 번의 비용은 거의 같으며, $v$에서 너비 우선 탐색을 한 번 수행하는 것이다.

나쁜 순서로 닫으면 갱신 횟수가 많아진다. Bob은 좋은 순서를 찾는 데 서툴러서, 매 단계마다 활성 노드 하나를 같은 확률로 무작위로 고른다. 갱신 횟수의 기댓값을 구하라.

정밀도 문제를 피하기 위해, 답이 기약분수 $p/q$로 나타내어질 때 $q r \equiv p \pmod{998244353}$을 만족하는 가장 작은 음이 아닌 정수 $r$을 출력하라. 예를 들어 $6 \times 166374072 \equiv 79$, $3 \times 332748131 \equiv 40 \pmod{998244353}$이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 정수 $n$으로 시작한다. 이어지는 $n$개의 줄에는 각각 두 정수 $u$, $v$가 주어지며, 이는 $u$번 노드와 $v$번 노드 사이의 간선을 나타낸다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그 테스트 케이스의 답이다.

• $1 \le T \le 100$
• $3 \le n \le 10^5$
• $1 \le u < v \le n$
• 모든 테스트 케이스의 $n$의 합은 $5 \times 10^5$을 넘지 않는다.
• 각 테스트 케이스의 간선은 서로 다르다. 즉, 다중 간선은 없다.