CF1889E Doremy's Swapping Trees

Consider two undirected graphs $ G_1 $ and $ G_2 $ . Every node in $ G_1 $ and in $ G_2 $ has a label. Doremy calls $ G_1 $ and $ G_2 $ similar if and only if: - The labels in $ G_1 $ are distinct, and the labels in $ G_2 $ are distinct. - The set $ S $ of labels in $ G_1 $ coincides with the set of labels in $ G_2 $ . - For every pair of two distinct labels $ u $ and $ v $ in $ S $ , the corresponding nodes are in the same connected component in $ G_1 $ if and only if they are in the same connected component in $ G_2 $ . Now Doremy gives you two trees $ T_1 $ and $ T_2 $ with $ n $ nodes, labeled from $ 1 $ to $ n $ . You can do the following operation any number of times: - Choose an edge set $ E_1 $ from $ T_1 $ and an edge set $ E_2 $ from $ T_2 $ , such that $ \overline{E_1} $ and $ \overline{E_2} $ are similar. Here $ \overline{E} $ represents the graph which is given by only reserving the edge set $ E $ from $ T $ (i.e., the edge-induced subgraph). In other words, $ \overline{E} $ is obtained from $ T $ by removing all edges not included in $ E $ and further removing all isolated vertices. - Swap the edge set $ E_1 $ in $ T_1 $ with the edge set $ E_2 $ in $ T_2 $ . Now Doremy is wondering how many distinct $ T_1 $ you can get after any number of operations. Can you help her find the answer? Output the answer modulo $ 10^9+7 $ .

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1\le t\le 2\cdot 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line contains an integer $ n $ ( $ 2\le n\le 10^5 $ ) — the number of nodes in the trees $ T_1 $ and $ T_2 $ . Each of the following $ n-1 $ lines contain two integers $ u,v $ ( $ 1\le u,v\le n $ ), representing an undirected edge in $ T_1 $ . It is guaranteed these edges form a tree. Each of the following $ n-1 $ lines contain two integers $ u,v $ ( $ 1\le u,v\le n $ ), representing an undirected edge in $ T_2 $ . It is guaranteed these edges form a tree. It is guaranteed that the sum of $ n $ does not exceed $ 2\cdot 10^5 $ .

For each test case, you should output a single line with an integer, representing the number of distinct $ T_1 $ after any number of operations, modulo $ 10^9+7 $ .

In the first test case, there is at most one distinct $ T_1 $ having the only edge $ (1,2) $ . In the second test case, you can choose the edge set $ \{(1,3),(2,3)\} $ in $ T_1 $ , the edge set $ \{(1,2),(2,3)\} $ in $ T_2 $ and swap them. So $ T_1 $ can be $ 1-3-2 $ or $ 1-2-3 $ . In the third test case, there are $ 4 $ distinct $ T_1 $ , as the following pictures.