# PROBLEM LINKS:

**DIFFICULTY:**

Easy

**PREREQUISITES:**

- Disjoint set union
- Sieve of Eratosthenes

**PROBLEM:**

Given an undirected connected graph with **N** nodes and
**N-1** edges.Let x_{ab} be the maximum edge weight
in the path a to b and y_{ab} be the minimum edge weight in the
path a to b.

**P** is equal to product of x_{ab} for all a,b such
that 1 <= a, b <= N where x_{ab} and x_{ba} is considered
same.

**Q** is equal to product of y_{ab} for all a,b such
that 1 <= a, b <= N where y_{ab} and y_{ba} is considered
same.

**Z** is equal to the maximum power to which Q can be raised
that when P is divided by it the remainder is 0.

Output P(mod 10^{9}+7), Q(mod 10^{9}+7) and Z.

**EXPLANATION :**

In a vector store the pair of nodes with their respective edge weights.
To get product of maximum weight between all pairs with (a,b) and (b,a) counted
once sort the vector in increasing order of edge weights.

Loop and get value of r[find(node1)] and r[find(node2)] (which provides number of nodes connected directly and indirectly to node1 and node2 including themselves), update the answer as
ans*power(weight,r[find(node1)]*r[find(node2)] and
take union(node1,node2) for every vector index.

For minimum weight do the above thing with vector sorted in decreasing order of weights.

Get P and Q in form of prime factors raised to respective powers using sieve and calculate Z.

**TIME COMPLEXITY:**

O(nlogn).