Lowest Medal Tiers at the Jam Fair

At a jam fair n jars numbered 0 .. n-1 each receive a tier, a positive integer (tier 1 is the lowest). The judges left notes [a, op, b]:

• op == "=": jars a and b are in the same tier;
• op == "<": jar a is in a strictly lower tier than jar b.

Assign tiers that satisfy every note and make every jar's tier as small as possible. (When the notes can be satisfied at all, one assignment is simultaneously smallest for every jar.) Return the list of tiers indexed by jar, or [] if no assignment satisfies all the notes.

Examples

Input:  n = 5, notes = [[0, "<", 1], [1, "=", 2], [3, "<", 2], [2, "<", 4], [0, "=", 3]]
Output: [1, 2, 2, 1, 3]
Explanation: the tie groups are {0, 3}, {1, 2} and {4}, and they must go
strictly upward in that order.

Input:  n = 3, notes = [[0, "=", 1], [1, "<", 2], [2, "<", 0]]
Output: []
Explanation: 0 and 1 share a tier, yet 1 < 2 < 0.

Input:  n = 2, notes = []
Output: [1, 1]

Constraints

• 1 <= n <= 10**5, 0 <= len(notes) <= 1.5 * 10**5, 0 <= a, b < n (a == b is allowed)
• Target: about O((n + N) * alpha(n)) time. Raising tiers note by note until nothing changes is far too slow on long chains.

Goals

• Merge tied items with union-find before building the order graph
• Detect both kinds of contradiction: a strict note inside one tie group, and a cycle between groups
• Give every group the smallest tier with a longest-path pass in topological order