24897번 - 숲 게임

BOJ 월드의 깊은 산 속 숭고한 협곡에는 $N$개의 나무로 구성된 숲이 있다. 이곳의 $i$번째 나무는 $M_i$개의 마디와 $M_i-1$개의 나뭇가지로 사이클 없이 연결되어 있다. A와 B는 여기에서 '숲 게임'을 할 것이다. '숲 게임'은 각 나무의 뿌리(1번 마디)에 돌을 하나씩 위치한 상태로 시작한다. 각 플레이어는 자신의 턴에 나무를 하나 선택하고, 그 나무의 돌을 아직 지나간 적 없는 인접한 나뭇가지를 따라서 $1$번 이상 최대 $K$번 이동시킨다. 게임을 시작하면 먼저 A의 턴이고, 이후 번갈아 가며 턴을 가지게 된다. 자신의 턴에 아무것도 움직일 수 없는(즉, 어떠한 나무에서도 이동 가능한 돌이 없는) 플레이어가 패배한다.

B가 나중에 시작하는 불리함을 보상하는 의미에서, 게임 시작 전에 B가 선택하는 몇 개의 나무만 게임에 사용하기로 했다. 단, 게임이 진행되기는 해야 하므로 B는 나무를 적어도 하나는 선택한다. 둘 다 최적으로 플레이할 때 B가 이길 수 있는 공집합이 아닌 나무 집합은 몇 개일까? 답이 너무 커질 수 있으므로 $998\,244\,353$으로 나눈 결과를 출력하자.

첫째 줄에 나무의 개수 $N$과 매 턴마다 움직일 수 있는 최대 횟수 $K$가 주어진다. $(1\leq N, K \leq 100\,000)$

그 후 $N$개의 나무 정보가 나무 번호의 오름차순으로 주어진다.

$i$번 나무의 정보의 첫째 줄에 나무의 마디 개수 $M_i$가 주어진다. $(1 \leq M_i,\ \sum M_i \leq 100\,000)$

다음 $M_i-1$개의 줄의 $j$번째 줄에 $j$번 나뭇가지가 연결하는 두 마디의 번호 $u_{i,j}, v_{i,j}$가 주어진다. $(1 \leq u_{i,j}, v_{i,j} \leq M_i,\ u_{i,j} \neq v_{i,j})$

연결하는 마디 쌍이 같은 나뭇가지가 여러 개 주어지지 않는다.

B가 이길 수 있는 공집합이 아닌 나무집합의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.