Unit Ratio Queries

ApplePhone screenMedium

A converter knows how some units of measure relate. There are n units numbered 0 to n - 1, and they fall into independent families (like length units or temperature units): units of the same family can be converted into each other, units of different families cannot. Each entry conversions[i] = [source, target, factor] says that one unit of source equals exactly factor units of target, and the conversion also works the other way: one unit of target equals 1 / factor units of source. Units that have no conversions are families of their own.

Part 1: Answering ratio queries

Implement unit_ratios(n, conversions, queries). Each query [a, b] asks how many units of b equal one unit of a.

If a == b, the answer is 1.
If a and b are in different families, the answer is -1.
Otherwise the exact answer is a fraction p / q in lowest terms; return p * q_inv modulo 1000000007, where q_inv is the modular inverse of q.

Return one answer per query, in order.

Example 1
n
6
queries
[[0,2],[2,0],[3,4],[4,3],[0,3],[5,5],[5,1]]
conversions
[[0,1,3],[2,1,5],[3,4,2]]
Output
[200000002,666666673,2,500000004,-1,1,-1]
Why: Units 0, 1, 2 form one family and 3, 4 another, while unit 5 stands alone. One unit 0 is 3 units 1 and one unit 2 is 5 units 1, so one unit 0 is 3/5 of a unit 2; 3/5 modulo 1000000007 is 200000002 because 5 * 200000002 leaves remainder 3. The reverse ratio 5/3 is 666666673. Units 3 and 4 give 2 and the inverse of 2. Units 0 and 3 are in different families, unit 5 against itself is 1, and unit 5 against any other unit is -1.
Example 2
n
4
queries
[[0,3],[3,0],[1,3],[2,2]]
conversions
[[0,1,2],[1,2,3],[2,3,5]]
Output
[30,233333335,15,1]
Why: One unit 0 is 2 units 1, which is 6 units 2, which is 30 units 3. Going the other way the ratio is 1/30, which is 233333335 modulo 1000000007 because 30 233333335 leaves remainder 1. Units 1 to 3 give 3 5 = 15, and a unit against itself is 1.

Constraints

1 <= n <= 10^5
0 <= len(conversions) <= n - 1
1 <= factor <= 10^9
1 <= len(queries) <= 10^5
0 <= a, b < n for every query
Any two units are joined by at most one chain of conversions, so conversions has no cycles

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question