Unit Ratio Queries Across Independent Unit Families with Modular Answers

There are n units of measure, numbered 0 to n - 1. The units fall into several independent families: units in the same family can be converted into one another, but a unit can never be converted into a unit of a different family (for example, length units form one family and temperature units form another). In this problem every conversion is a pure multiplicative factor; scales that also need an offset are out of scope.

You are given a list conversions, where conversions[i] = [source, target, factor] states that one unit of source equals exactly factor units of target. Every conversion also works in reverse: one unit of target equals 1/factor units of source. Conversions chain: if one unit of a equals 2 units of b, and one unit of b equals 3 units of c, then one unit of a equals 6 units of c.

You are also given a list queries, where queries[j] = [a, b] asks: how many units of b equal one unit of a?

Function Signature

def unit_ratios(n: int, conversions: list[list[int]], queries: list[list[int]]) -> list[int]:

Rules

• Two units belong to the same family exactly when a chain of conversions, each usable in either direction, connects them. A unit that appears in no conversion forms a family by itself.
• If a and b belong to the same family, write the exact answer as a fraction p / q in lowest terms, and return (p * q_inv) % 1_000_000_007, where q_inv is the modular multiplicative inverse of q modulo the prime 1_000_000_007.
• If a == b, the answer is 1.
• If a and b belong to different families, the answer is -1.
• Return one answer per query, in the same order as queries.

Constraints

• 1 <= n <= 10**5
• 0 <= len(conversions) <= n - 1
• 0 <= source, target <= n - 1 and source != target
• 1 <= factor <= 10**9
• The conversions contain no cycle: between any two units there is at most one chain of conversions (ignoring direction), and no pair of units is given more than one conversion. Each family is therefore a tree, and the input is never contradictory.
• 1 <= len(queries) <= 10**5
• 0 <= a, b <= n - 1
• Every answer is -1 or an integer in [0, 1_000_000_006], which fits in a 32-bit signed integer. The product of two such residues can reach about 10**18, which exceeds the 32-bit range, so languages without arbitrary-precision integers need 64-bit arithmetic for intermediate products.

Examples

Example 1

Input: n = 5
 conversions = [[0, 1, 2], [1, 2, 3], [3, 4, 4]]
 queries = [[0, 2], [2, 0], [1, 0], [3, 4], [4, 3], [0, 4], [2, 2]]
Output: [6, 166666668, 500000004, 4, 250000002, -1, 1]

Units 0, 1 and 2 form one family, and units 3 and 4 form another. One unit of 0 is 2 units of 1, which is 6 units of 2, so [0, 2] gives 6. The query [2, 0] asks for 1/6, which is 166666668 because 6 * 166666668 = 1000000008, which is 1 modulo 1_000_000_007. Likewise [1, 0] is 1/2, giving 500000004; [3, 4] is 4; [4, 3] is 1/4, giving 250000002. The query [0, 4] crosses families, so it gives -1, and [2, 2] gives 1.

Example 2

Input: n = 3
 conversions = [[0, 1, 2], [0, 2, 3]]
 queries = [[1, 2], [2, 1]]
Output: [500000005, 666666672]

One unit of 1 is 1/2 unit of 0, which is 3/2 units of 2, and 3 * 500000004 = 1500000012, which is 500000005 modulo 1_000_000_007. One unit of 2 is 1/3 unit of 0, which is 2/3 units of 1, and 2 * 333333336 = 666666672.

Example 3

Input: n = 4
 conversions = [[0, 1, 1000000000], [1, 2, 1000000000]]
 queries = [[0, 2], [3, 3], [3, 0]]
Output: [49, 1, -1]

One unit of 0 is 10**18 units of 2. Since 10**18 = (10**9 + 7) * (10**9 - 7) + 49, the answer is 49. Unit 3 appears in no conversion, so it forms its own family: [3, 3] gives 1 and [3, 0] gives -1.