You are given a list of riders and a chronological list of Uber Share events. Each shared-ride event connects two riders. Two riders are connected if they have directly or indirectly shared rides through other riders.

Return the earliest timestamp when all riders become part of one connected shared-ride network. If all riders never become connected, return -1.

Method Signature

long earliestFullConnectivityTimestamp(List<String> riders, List<String> logs)

• riders contains all possible riders.
• logs contains ride-sharing events sorted by timestamp in non-decreasing order.
• Each log is in the format "timestamp,rider1,rider2".
• "timestamp,Alice,Bob" means Alice shared a ride with Bob at that timestamp.
• Return the first timestamp when every rider belongs to the same connected component.

Follow Up:

long earliestFullConnectivityTimestampWithBlocks(List<String> riders, List<String> logs)

• This method supports both sharing and blocking events.
• Each log is in the format "timestamp,eventType,rider1,rider2".
• eventType is either "SHARE" or "BLOCK".
• "timestamp,SHARE,Alice,Bob" adds a connection between Alice and Bob.
• "timestamp,BLOCK,Alice,Bob" removes the direct connection between Alice and Bob, if it exists.
• After each event, check whether all riders are connected using the currently active share connections.
• Return the earliest timestamp when all riders are connected, or -1 if it never happens.

Rules

• Rider names are case-sensitive strings. They do not contain comma characters and do not contain leading or trailing spaces.
• Each rider in a log will exist in riders.
• A rider will not share a ride with themselves.
• Duplicate share events between the same two riders should not create multiple separate connections.
• For the follow up, blocking one pair only removes the direct connection between that pair.
• Connectivity through other riders may still exist after a block event.
• If riders contains exactly one rider, return 0.
• The output is deterministic because the earliest timestamp in chronological order is always returned.

Constraints

• 1 ≤ riders.size() ≤ 100,000
• 0 ≤ logs.size() ≤ 200,000
• 1 ≤ rider.length() ≤ 50
• 0 ≤ timestamp ≤ 999,999,999,999
• Logs are sorted by timestamp in non-decreasing order.
• Parameter values will not be null.

Follow Up Method Additional Constraints

• 1 ≤ riders.size() ≤ 2,000
• 0 ≤ logs.size() ≤ 10,000
• Each log is in the format "timestamp,eventType,rider1,rider2".
• eventType is either "SHARE" or "BLOCK".

Examples

Example 1

earliestFullConnectivityTimestamp(riders = ["Ava", "Ben", "Cara", "Dev"], logs = ["101,Ava,Ben", "105,Cara,Dev", "110,Ben,Cara"])

Output: 110

Explanation: At timestamp 110, the groups Ava-Ben and Cara-Dev become connected through Ben-Cara.

Example 2

earliestFullConnectivityTimestamp(riders = ["Mia", "Noah", "Omar"], logs = ["200,Mia,Noah"])

Output: -1

Explanation: Omar never becomes connected with the other riders.

Example 3

earliestFullConnectivityTimestamp(riders = ["Zara"], logs = [])

Output: 0

Explanation: A single rider is already fully connected.

Example 4

earliestFullConnectivityTimestampWithBlocks(riders = ["A", "B", "C"], logs = ["10,SHARE,A,B", "20,SHARE,B,C"])

Output: 20

Explanation: At timestamp 20, all riders are connected through active share connections.

Example 5

earliestFullConnectivityTimestampWithBlocks(riders = ["A", "B", "C"], logs = ["10,SHARE,A,B", "15,BLOCK,A,B", "20,SHARE,B,C", "25,SHARE,A,C"])

Output: 25

Explanation: The connection between A and B is removed at timestamp 15. All riders become connected only after A shares with C at timestamp 25.