You are given c power stations labeled from $1$ to c, and an undirected network described by connections, where each pair [u, v] means stations u and v are directly connected. These connections define connected components (power grids).

Initially, every station is online.

You must process queries in order. Each query is a pair [type, x] with the following meaning.

• If type equals $1$, perform a maintenance check for station x and return a station id as follows.

  • If station x is currently online, return x.

  • Otherwise, consider the connected component (in the original graph defined by connections) that contains x, and among the stations in that component that are currently online, return the smallest station id. If no station in that component is online, return $-1$.

• If type equals $2$, station x goes offline. Once a station is offline, it stays offline for the rest of the queries.

Return an array containing the results of all queries with type equal to $1$, in the same order they appear.

Constraints:

• $1 \leq$ c $\leq 10^5$

• $0 \leq$ n $==$ connections.length $\leq \min\left(10^5, \frac{c \cdot (c - 1)}{2}\right)$

• connections[i].length $==$ $2$

• $1 \leq$ u_i, v_i $\leq$ c

• u_i $\neq$ v_i

• $1 \leq$ queries.length $\leq 2 \cdot 10^5$

• queries[i].length $==$ $2$

• queries[i][0] is either $1$ or $2$

• $1 \leq$ queries[i][1] $\leq$ c

Input: c = 6-int, connections = [[1,2],[2,3],[4,5]]-List[List[int]], queries = [[1,3],[2,2],[1,2],[2,1],[1,3],[1,6],[2,6],[1,6],[2,4],[1,5]]-List[List[int]]
Output: [3, 1, 3, 6, -1, 5]-List[int]
Explanation: The graph has components {1,2,3}, {4,5}, and {6}, and all stations start online. [1,3] returns 3 (online); [2,2] takes station 2 offline; [1,2] finds 2 offline, so the smallest online station in {1,2,3} is 1; [2,1] takes 1 offline; [1,3] returns 3; [1,6] returns 6; [2,6] takes 6 offline; [1,6] returns -1 since {6} has no online stations; [2,4] takes 4 offline; and [1,5] returns 5. The collected type 1 outputs are [3, 1, 3, 6, -1, 5].

Input: c = 4-int, connections = [[1,2],[2,3],[3,4]]-List[List[int]], queries = [[2,2],[2,3],[1,2],[2,1],[2,4],[1,3]]-List[List[int]]
Output: [1, -1]-List[int]
Explanation: All stations are in one component {1,2,3,4}. [2,2] and [2,3] take 2 and 3 offline; [1,2] finds 2 offline, so the smallest online station among {1,4} is 1; [2,1] and [2,4] take 1 and 4 offline; and [1,3] finds no online stations left, returning -1. The outputs are [1, -1].

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.