1class UnionFind {
2    // Parent array: p[i] stores the parent of node i
3    private final int[] p;
4    // Size array: size[i] stores the size of the tree rooted at i
5    private final int[] size;
6
7    public UnionFind(int n) {
8        p = new int[n];
9        size = new int[n];
10        // Initially every node is its own root with size 1
11        for (int i = 0; i < n; ++i) {
12            p[i] = i;
13            size[i] = 1;
14        }
15    }
16
17    /**
18     * Finds the root of node x with path compression.
19     *
20     * @param x the node to query
21     * @return the root representative of the set containing x
22     */
23    public int find(int x) {
24        if (p[x] != x) {
25            // Path compression: point x directly to the root
26            p[x] = find(p[x]);
27        }
28        return p[x];
29    }
30
31    /**
32     * Merges the sets containing a and b using union by size.
33     *
34     * @param a the first node
35     * @param b the second node
36     * @return true if a merge happened, false if they were already connected
37     */
38    public boolean union(int a, int b) {
39        int pa = find(a), pb = find(b);
40        // Already in the same set, no merge needed
41        if (pa == pb) {
42            return false;
43        }
44        // Attach the smaller tree under the larger one
45        if (size[pa] > size[pb]) {
46            p[pb] = pa;
47            size[pa] += size[pb];
48        } else {
49            p[pa] = pb;
50            size[pb] += size[pa];
51        }
52        return true;
53    }
54}
55
56class Solution {
57    public int[] processQueries(int c, int[][] connections, int[][] queries) {
58        // Build the disjoint set over nodes 1..c (index 0 unused)
59        UnionFind uf = new UnionFind(c + 1);
60        for (int[] e : connections) {
61            uf.union(e[0], e[1]);
62        }
63
64        // For each connected component (keyed by its root), maintain an
65        // ordered set of currently online nodes so we can quickly fetch
66        // the smallest available node.
67        TreeSet<Integer>[] st = new TreeSet[c + 1];
68        Arrays.setAll(st, k -> new TreeSet<>());
69        for (int i = 1; i <= c; i++) {
70            int root = uf.find(i);
71            st[root].add(i);
72        }
73
74        List<Integer> ans = new ArrayList<>();
75        for (int[] q : queries) {
76            int a = q[0], x = q[1];
77            // Identify the component that node x belongs to
78            int root = uf.find(x);
79
80            if (a == 1) {
81                // Type 1 query: report a usable node in x's component
82                if (st[root].contains(x)) {
83                    // x itself is online, prefer returning x
84                    ans.add(x);
85                } else if (!st[root].isEmpty()) {
86                    // Otherwise return the smallest online node in the component
87                    ans.add(st[root].first());
88                } else {
89                    // No online node available in the component
90                    ans.add(-1);
91                }
92            } else {
93                // Type 2 query: take node x offline
94                st[root].remove(x);
95            }
96        }
97
98        // Convert the result list to a primitive int array
99        return ans.stream().mapToInt(Integer::intValue).toArray();
100    }
101}
102

1class UnionFind {
2public:
3    // Initialize the union-find structure with n elements (indices 0..n-1).
4    UnionFind(int n) {
5        parent = vector<int>(n);
6        componentSize = vector<int>(n, 1);
7        // Each element starts as its own root: parent[i] = i.
8        iota(parent.begin(), parent.end(), 0);
9    }
10
11    // Merge the sets containing a and b.
12    // Returns false if they already belong to the same set, true otherwise.
13    bool unite(int a, int b) {
14        int rootA = find(a), rootB = find(b);
15        if (rootA == rootB) {
16            return false;
17        }
18        // Union by size: attach the smaller tree under the larger one.
19        if (componentSize[rootA] > componentSize[rootB]) {
20            parent[rootB] = rootA;
21            componentSize[rootA] += componentSize[rootB];
22        } else {
23            parent[rootA] = rootB;
24            componentSize[rootB] += componentSize[rootA];
25        }
26        return true;
27    }
28
29    // Find the root representative of x with path compression.
30    int find(int x) {
31        if (parent[x] != x) {
32            parent[x] = find(parent[x]);
33        }
34        return parent[x];
35    }
36
37private:
38    vector<int> parent;         // parent[i] points to the parent of node i
39    vector<int> componentSize;  // componentSize[root] holds the size of the component
40};
41
42class Solution {
43public:
44    vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
45        // Build the connected components from the given connections.
46        // Use indices 1..c, so allocate c + 1 slots.
47        UnionFind uf(c + 1);
48        for (auto& edge : connections) {
49            uf.unite(edge[0], edge[1]);
50        }
51
52        // For each component root, store its online stations in a sorted set,
53        // so the smallest available station can be retrieved quickly.
54        vector<set<int>> componentStations(c + 1);
55        for (int i = 1; i <= c; i++) {
56            componentStations[uf.find(i)].insert(i);
57        }
58
59        vector<int> ans;
60        for (auto& query : queries) {
61            int type = query[0], station = query[1];
62            int root = uf.find(station);
63            if (type == 1) {
64                // Type 1: query the maintenance station for the given station.
65                if (componentStations[root].count(station)) {
66                    // The station itself is online; answer with it.
67                    ans.push_back(station);
68                } else if (!componentStations[root].empty()) {
69                    // Otherwise return the smallest online station in the component.
70                    ans.push_back(*componentStations[root].begin());
71                } else {
72                    // No online station available in this component.
73                    ans.push_back(-1);
74                }
75            } else {
76                // Type 2: take the station offline by removing it from its component.
77                componentStations[root].erase(station);
78            }
79        }
80        return ans;
81    }
82};
83

1// Global union-find arrays.
2let parent: number[] = [];        // parent[i] points to the parent of node i
3let componentSize: number[] = []; // componentSize[root] holds the size of the component
4
5// Initialize the union-find structure with n elements (indices 0..n-1).
6function init(n: number): void {
7    parent = new Array(n);
8    componentSize = new Array(n).fill(1);
9    // Each element starts as its own root: parent[i] = i.
10    for (let i = 0; i < n; i++) {
11        parent[i] = i;
12    }
13}
14
15// Find the root representative of x with path compression.
16function find(x: number): number {
17    if (parent[x] !== x) {
18        parent[x] = find(parent[x]);
19    }
20    return parent[x];
21}
22
23// Merge the sets containing a and b.
24// Returns false if they already belong to the same set, true otherwise.
25function unite(a: number, b: number): boolean {
26    const rootA = find(a);
27    const rootB = find(b);
28    if (rootA === rootB) {
29        return false;
30    }
31    // Union by size: attach the smaller tree under the larger one.
32    if (componentSize[rootA] > componentSize[rootB]) {
33        parent[rootB] = rootA;
34        componentSize[rootA] += componentSize[rootB];
35    } else {
36        parent[rootA] = rootB;
37        componentSize[rootB] += componentSize[rootA];
38    }
39    return true;
40}
41
42// A simple binary min-heap of numbers, used to emulate C++'s ordered set
43// for quickly retrieving the smallest online station in a component.
44class MinHeap {
45    private data: number[] = [];
46
47    // Push a value into the heap, sifting it up to its correct position.
48    push(value: number): void {
49        this.data.push(value);
50        let i = this.data.length - 1;
51        while (i > 0) {
52            const parentIdx = (i - 1) >> 1;
53            if (this.data[parentIdx] <= this.data[i]) {
54                break;
55            }
56            [this.data[parentIdx], this.data[i]] = [this.data[i], this.data[parentIdx]];
57            i = parentIdx;
58        }
59    }
60
61    // Return the smallest value without removing it.
62    top(): number {
63        return this.data[0];
64    }
65
66    // Remove and return the smallest value, sifting the last element down.
67    pop(): number {
68        const top = this.data[0];
69        const last = this.data.pop()!;
70        if (this.data.length > 0) {
71            this.data[0] = last;
72            let i = 0;
73            const n = this.data.length;
74            while (true) {
75                const left = 2 * i + 1;
76                const right = 2 * i + 2;
77                let smallest = i;
78                if (left < n && this.data[left] < this.data[smallest]) {
79                    smallest = left;
80                }
81                if (right < n && this.data[right] < this.data[smallest]) {
82                    smallest = right;
83                }
84                if (smallest === i) {
85                    break;
86                }
87                [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
88                i = smallest;
89            }
90        }
91        return top;
92    }
93
94    // Whether the heap currently holds no elements.
95    empty(): boolean {
96        return this.data.length === 0;
97    }
98}
99
100function processQueries(c: number, connections: number[][], queries: number[][]): number[] {
101    // Build the connected components from the given connections.
102    // Use indices 1..c, so allocate c + 1 slots.
103    init(c + 1);
104    for (const edge of connections) {
105        unite(edge[0], edge[1]);
106    }
107
108    // For each component root, store its online stations in a min-heap,
109    // so the smallest available station can be retrieved quickly.
110    const componentStations: MinHeap[] = new Array(c + 1);
111    for (let i = 0; i <= c; i++) {
112        componentStations[i] = new MinHeap();
113    }
114    // Track whether each station is currently online (not taken offline).
115    const online: boolean[] = new Array(c + 1).fill(true);
116
117    for (let i = 1; i <= c; i++) {
118        componentStations[find(i)].push(i);
119    }
120
121    const ans: number[] = [];
122    for (const query of queries) {
123        const type = query[0];
124        const station = query[1];
125        const root = find(station);
126        if (type === 1) {
127            // Type 1: query the maintenance station for the given station.
128            if (online[station]) {
129                // The station itself is online; answer with it.
130                ans.push(station);
131            } else {
132                // Otherwise return the smallest online station in the component,
133                // lazily discarding heap tops that are already offline.
134                const heap = componentStations[root];
135                while (!heap.empty() && !online[heap.top()]) {
136                    heap.pop();
137                }
138                if (!heap.empty()) {
139                    ans.push(heap.top());
140                } else {
141                    // No online station available in this component.
142                    ans.push(-1);
143                }
144            }
145        } else {
146            // Type 2: take the station offline by marking it offline.
147            online[station] = false;
148        }
149    }
150    return ans;
151}
152