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 ```python 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** ```text 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** ```text 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** ```text 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`.