Codeforces Round 906 (Div. 1) |
---|
Finished |
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:
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:
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$$$.
321 22 131 32 32 32 141 22 33 44 22 11 3
1 2 4
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.
Name |
---|