通讯网络（network）

【题目描述】

城市的通讯网络被不法分子彻底切断了，所有通讯通道全部断开了。现在需要将 n 个 通讯服务器重新连接，编号为 1 到 n。上级共下发了 n - 1 条命令，每条命令包含两个还未 处在同一通讯网络的服务器 ai，bi。AI 机器人会按次序执行这些命令，对于第 i 条命令，AI 机器人会随机选取 ai 所在的通讯网络中的某个服务器与 bi 所在的通讯网络中的某个服务器， 将这两个点间建立通讯通道，通讯通道是双向的。其中，“通讯网络”的定义为：若服务器 a 能通过若干条通讯通道到达服务器 b，则称服务器 a 与服务器 b 在一个通讯网络内。可以 证明，当 n - 1 条命令执行完毕后，n 个通讯服务器将处于同一个通讯网络内。 现在，身为 AI 工程师的你想知道，这些 AI 机器人建立的新的通讯网络，有多大概率和 原本的通讯网络是相同的（即所有通讯通道所处的位置都是一样的）。你只需要输出概率取 模 998244353 后的结果。 注意：概率可能为 0，也就是不可能建立与原本通讯网络相同的网络。

【输入格式】

从文件 network.in 中读入数据。 输入包含多组数据。 第一行包含一个正整数 T，表示数据组数。 接下来对于每组数据： 第一行包含一个正整数 n，表示通讯服务器的数量。 接下来 n – 1 行，每行包含两个正整数 ai，bi。 接下来 n – 1 行，每行包含两个正整数 ui，vi，表示在原本的通讯网络中服务器 ui 与 服务器 vi 之间有一个通讯通道。数据保证原本的通讯网络中的 n 个点一定处在同一通讯网 络。

【输出格式】

输出到文件 network.out 中。 输出共 T 行，每行一个整数，表示原本相同的概率。（对结果取模 998244353）

【样例 1 输入】

1

3

1 2

1 3

1 2

1 3

【样例 1 输出】

499122177

【数据规模】

对于所有测试数据，1 ≤ n ≤ 2×10^5，1 ≤ T ≤ 10，1 ≤ ai, bi, ui, vi ≤ n – 1， 数据保证原本的通讯网络中的 n 个点一定处在同一通讯网络。