A club has n members numbered 0 .. n-1. The list log records meetings as triples [t, a, b]: at time t, members a and b met. Two members are linked at time T if a chain of meetings that happened at times <= T joins them (for example, a met c and later c met b).
The log is not sorted. Return the earliest time at which every member is linked to every other member, or -1 if that never happens.
Examples
Input: n = 4, log = [[5, 0, 1], [2, 2, 3], [9, 1, 2], [7, 0, 1]]
Output: 9
Explanation: by time 5 the groups are {0, 1} and {2, 3}; the meeting at time 9 joins them.
Input: n = 3, log = [[1, 0, 1], [4, 0, 1]]
Output: -1
Input: n = 3, log = [[3, 0, 2], [3, 1, 2]]
Output: 3
Constraints
2 <= n <= 10**4,0 <= len(log) <= 2 * 10**4,0 <= t <= 10**9,0 <= a, b < n; several meetings may share a time- Target: O(L log L + L * alpha(n)) time.
Goals
- Process timestamped events in chronological order
- Stop as soon as the component count reaches one