Find earliest time all riders become connected

You are given a time-ordered log of events involving Uber riders. Each event has a timestamp and two rider names.

Event types:

1. t X shared-ride-with Y — riders X and Y shared a ride at time t, which creates an (undirected) connection between them.

Two riders are considered connected if there is a path of shared rides between them (transitive connectivity). For example, if A shared with B and B shared with C, then A is connected to C.

Example (already sorted by time):

• t1 Alice shared-ride-with Bob
• t2 Charlie shared-ride-with Dan
• t3 Bob shared-ride-with Charlie
• t4 Alice shared-ride-with Eve
• t5 Bob shared-ride-with Dan

Task:

• Return the earliest timestamp at which all riders that appear in the logs become connected in a single connected component. If this never happens, return an appropriate value (e.g., -1).

Follow-up: The log may also contain block events:

• t X blocked Y — starting at time t, treat riders X and Y as no longer directly connected by their shared-ride relationship (i.e., the edge between X and Y is removed for times >= t, even if they shared earlier).

How would you modify your approach to still find the earliest time when all riders are connected, given that connections can be both added (shared-ride-with) and removed (blocked)?

Part 1: Earliest Time All Riders Become Connected

You are given a time-ordered list of shared-ride events. Each event is a tuple (timestamp, rider_a, rider_b) meaning rider_a and rider_b shared a ride at that time, creating an undirected connection between them. Two riders are considered connected if there is a path of shared rides between them. Return the earliest timestamp at which all riders that appear anywhere in the log belong to a single connected component. If this never happens, return -1.

Constraints

• 0 <= len(events) <= 2 * 10^5
• Timestamps are strictly increasing integers.
• rider_a and rider_b are non-empty strings.
• rider_a != rider_b for every event.
• All riders that appear anywhere in the log must be considered when deciding connectivity.

Examples

Example 1

Input: [(1, 'Alice', 'Bob'), (2, 'Charlie', 'Dan'), (3, 'Bob', 'Charlie'), (4, 'Alice', 'Eve'), (5, 'Bob', 'Dan')]
Output: 4

Explanation: After time 3, Alice/Bob/Charlie/Dan are connected, but Eve is still separate. At time 4, Eve joins the same component, so the answer is 4.

Example 2

Input: [(1, 'A', 'B'), (2, 'A', 'B'), (3, 'B', 'C')]
Output: 3

Explanation: The duplicate edge at time 2 changes nothing. All three riders become connected at time 3.

Hints

1. Model riders as nodes in an undirected graph, and process edges in time order.
2. If you know the full set of riders in advance, a Disjoint Set Union (Union-Find) can track how many connected components remain.

Part 2: Earliest Time All Riders Become Connected with Shared and Blocked Events

You are given a time-ordered list of rider events. Each event is a tuple (timestamp, action, rider_a, rider_b). If action == 'shared', riders rider_a and rider_b become directly connected from that time onward. If action == 'blocked', the direct edge between rider_a and rider_b is removed from that time onward. A later shared event for the same pair can add the edge again. Connectivity is still transitive through other riders. Return the earliest timestamp at which all riders that appear anywhere in the full log are connected at the same time. If this never happens, return -1.

Constraints

• 0 <= len(events) <= 2 * 10^5
• Timestamps are strictly increasing integers.
• action is either 'shared' or 'blocked'.
• rider_a and rider_b are non-empty strings, and rider_a != rider_b.
• The same pair may appear many times.
• A blocked event for a pair that is not currently active has no effect.
• All riders that appear anywhere in the log, including riders that only appear in block events, count toward the final connectivity check.

Examples

Example 1

Input: [(1, 'shared', 'Alice', 'Bob'), (2, 'shared', 'Charlie', 'Dan'), (3, 'shared', 'Bob', 'Charlie'), (4, 'blocked', 'Alice', 'Bob')]
Output: 3

Explanation: At time 3, all four riders are connected. The later block at time 4 breaks one direct edge, but the earliest successful time is still 3.

Example 2

Input: [(1, 'shared', 'A', 'B'), (2, 'shared', 'B', 'C'), (3, 'blocked', 'B', 'C'), (4, 'shared', 'C', 'A')]
Output: 2

Explanation: All riders are already connected at time 2. Even though they disconnect later and reconnect again, the earliest valid time is 2.

Hints

1. A normal Union-Find handles edge additions well, but not deletions. Try processing the problem offline instead of updating one mutable graph directly.
2. Think about the time interval during which each edge is active, then add that edge to a segment tree over time and use a rollback DSU while traversing it.