Unique Configuration Permutations in Forest Graphs

You are given a forest with n nodes. Each node is associated with an integer value (which is not used in the computation). The forest is described by m edges connecting some of the nodes. Initially, you have a configuration where each node holds a unique value. You are allowed to perform the following operation any number of times: select any two adjacent nodes (i.e. nodes directly connected by an edge) and swap their values. Two configurations are considered different if there exists at least one node which has a different integer value in the two configurations.

Your task is to compute the number of distinct configurations possible by performing any sequence of valid swaps. It can be shown that the answer is the product of the factorials of the sizes of the connected components of the forest. Output the result modulo \(10^9+7\).

inputFormat

The first line of input contains a single integer T denoting the number of test cases.

For each test case, the input is given as follows:

• The first line contains an integer n representing the number of nodes.
• The second line contains n space-separated integers representing the initial values associated with the nodes.
• The third line contains an integer m representing the number of edges in the graph.
• Each of the next m lines contains two space-separated integers u and v indicating that there is an edge connecting node u and node v (the nodes are 1-indexed).

outputFormat

For each test case, output a single integer on a new line representing the number of distinct configurations modulo \(10^9+7\>.

## sample

3
3
1 2 3
2
1 2
2 3
4
1 2 3 4
3
1 2
1 3
1 4
1
1
0

6
24
1

</p>