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.

Multiplicative Unit Conversion Queries Modulo a Prime

Hints

1. Every conversion can be used in both directions: moving from target back to source divides by the factor instead of multiplying by it.
2. A chain of factors of 109 makes the exact ratio astronomically large, so keep every quantity as a residue modulo 1_000_000_007. Because every factor is between 1 and 109, none is divisible by the prime, so every division can be carried out with a modular inverse.
3. Two units in different families answer -1, while a unit asked about itself answers 1 even when it appears in no conversion.

Approach

Algorithm: treat every conversion [source, target, factor] as two directed adjacency entries: source -> target multiplies by factor, and target -> source divides by factor. Scan units 0..n-1; each unvisited unit becomes the root of a new family and an iterative depth-first search (explicit stack) labels every reachable unit with that root. For every reached unit v it records r[v] = the number of units of v that equal one unit of the root, kept as a pair of residues num[v] / den[v] modulo P = 1_000_000_007: crossing a forward edge multiplies the numerator by factor, crossing a reverse edge multiplies the denominator by factor.

Invariant: when v is labelled, num[v] * inverse(den[v]) is congruent to the exact rational r[v]. Each family is a tree, so v is reached along its unique path from the root and r[v] is exactly the product of the edge ratios along that path; no conflicting second path exists.

Answering a query [a, b]: if a == b return 1; if the two units have different roots return -1. Otherwise one unit of a equals 1 / r[a] root units, which equals r[b] / r[a] units of b, so the answer is num[b] * den[a] times the modular inverse of den[b] * num[a], computed with Fermat's little theorem as x^(P-2) mod P.

Correctness of the modular value: every factor lies in [1, 10**9], below the prime P, so no product of factors is divisible by P and every inverse exists. Reduction modulo P is a ring homomorphism on fractions whose denominator is coprime to P, so the unreduced fraction the search builds (for example 18/8) maps to the same residue as its lowest-terms form p/q (9/4), which is exactly (p * q_inv) % P as required.

Edge cases: units in no conversion are their own family (self query 1, anything else -1); empty conversions; duplicate queries are answered independently in order; residue products reach about 10**18, so Java and C++ use 64-bit integers and JavaScript splits each multiplication so every intermediate stays below 2^53; the explicit stack avoids recursion-depth failures on long chains.

• Time complexity: O(n + m + q log P), where m = len(conversions), q = len(queries) and P = 1_000_000_007
• Space complexity: O(n + m)