1/**
2 * Weighted Union-Find (Disjoint Set Union) with path compression
3 * and union by size.
4 */
5class UnionFind {
6    // parent[i] holds the parent of node i; root nodes point to themselves
7    private int[] parent;
8    // size[i] holds the number of nodes in the tree rooted at i
9    private int[] size;
10    // count of connected components
11    int count;
12
13    UnionFind(int n) {
14        parent = new int[n];
15        size = new int[n];
16        count = n;
17        // Initially every node is its own root, each component has size 1
18        for (int i = 0; i < n; i++) {
19            parent[i] = i;
20            size[i] = 1;
21        }
22    }
23
24    /**
25     * Find the root representative of x, applying path compression.
26     */
27    int find(int x) {
28        if (parent[x] != x) {
29            parent[x] = find(parent[x]);
30        }
31        return parent[x];
32    }
33
34    /**
35     * Merge the components containing a and b (union by size).
36     * Returns true if a merge actually happened, false if already connected.
37     */
38    boolean union(int a, int b) {
39        int rootA = find(a);
40        int rootB = find(b);
41        if (rootA == rootB) {
42            return false;
43        }
44        // Attach the smaller tree under the larger one to keep depth low
45        if (size[rootA] > size[rootB]) {
46            parent[rootB] = rootA;
47            size[rootA] += size[rootB];
48        } else {
49            parent[rootA] = rootB;
50            size[rootB] += size[rootA];
51        }
52        count--;
53        return true;
54    }
55}
56
57class Solution {
58
59    private int n;                 // number of nodes
60    private int[][] edges;         // edge list: [u, v, strength, mustUse]
61    private int k;                 // number of edges we may "upgrade" (double strength)
62
63    /**
64     * Feasibility check for the binary search.
65     * Returns true if the graph can be fully connected such that every used
66     * edge has an effective strength >= limit.
67     *
68     * Two passes are performed:
69     *   1) Use edges whose original strength already meets the limit.
70     *   2) Use up to k "upgraded" edges whose doubled strength meets the limit.
71     */
72    private boolean check(int limit) {
73        UnionFind uf = new UnionFind(n);
74
75        // Pass 1: connect using edges that satisfy the limit without upgrading
76        for (int[] edge : edges) {
77            int u = edge[0];
78            int v = edge[1];
79            int strength = edge[2];
80            if (strength >= limit) {
81                uf.union(u, v);
82            }
83        }
84
85        // Pass 2: connect using upgraded edges (strength * 2), limited to k upgrades
86        int remaining = k;
87        for (int[] edge : edges) {
88            int u = edge[0];
89            int v = edge[1];
90            int strength = edge[2];
91            if (strength * 2 >= limit && remaining > 0) {
92                // Only consume an upgrade if it actually merges two components
93                if (uf.union(u, v)) {
94                    remaining--;
95                }
96            }
97        }
98
99        // Connected iff exactly one component remains
100        return uf.count == 1;
101    }
102
103    public int maxStability(int n, int[][] edges, int k) {
104        this.n = n;
105        this.edges = edges;
106        this.k = k;
107
108        UnionFind uf = new UnionFind(n);
109        // Track the minimum strength among mandatory edges; this caps the answer
110        int minMustStrength = (int) 1e6;
111
112        // Step 1: process mandatory edges (must == 1)
113        for (int[] edge : edges) {
114            int u = edge[0];
115            int v = edge[1];
116            int strength = edge[2];
117            int must = edge[3];
118            if (must == 1) {
119                minMustStrength = Math.min(minMustStrength, strength);
120                // If a mandatory edge forms a cycle, the configuration is invalid
121                if (!uf.union(u, v)) {
122                    return -1;
123                }
124            }
125        }
126
127        // Step 2: add all remaining edges to test overall connectivity
128        for (int[] edge : edges) {
129            uf.union(edge[0], edge[1]);
130        }
131
132        // If the graph cannot be fully connected at all, return -1
133        if (uf.count > 1) {
134            return -1;
135        }
136
137        // Step 3: binary search the maximum achievable minimum stability.
138        // The answer cannot exceed minMustStrength (mandatory edges are always used).
139        int left = 1;
140        int right = minMustStrength;
141        while (left < right) {
142            // Upper-mid to avoid infinite loop when searching for the max feasible value
143            int mid = (left + right + 1) >>> 1;
144            if (check(mid)) {
145                left = mid;   // mid is feasible, try to go higher
146            } else {
147                right = mid - 1; // mid is infeasible, lower the bound
148            }
149        }
150
151        return left;
152    }
153}
154

1class UnionFind {
2public:
3    vector<int> parent;     // parent[i] = parent of node i in the disjoint set
4    vector<int> rankSize;   // rankSize[i] = size of the set rooted at i
5    int count;              // number of disjoint connected components
6
7    explicit UnionFind(int n) {
8        parent.resize(n);
9        rankSize.assign(n, 1);
10        count = n;
11        // Initially every node is its own root
12        for (int i = 0; i < n; ++i) {
13            parent[i] = i;
14        }
15    }
16
17    // Find the root of x with path compression
18    int find(int x) {
19        if (parent[x] != x) {
20            parent[x] = find(parent[x]);
21        }
22        return parent[x];
23    }
24
25    // Merge the sets containing a and b (union by size).
26    // Returns true if a merge happened, false if they were already connected.
27    bool unite(int a, int b) {
28        int rootA = find(a), rootB = find(b);
29        if (rootA == rootB) {
30            return false;
31        }
32        // Attach the smaller tree under the larger one
33        if (rankSize[rootA] > rankSize[rootB]) {
34            parent[rootB] = rootA;
35            rankSize[rootA] += rankSize[rootB];
36        } else {
37            parent[rootA] = rootB;
38            rankSize[rootB] += rankSize[rootA];
39        }
40        --count;
41        return true;
42    }
43};
44
45class Solution {
46public:
47    int n;                       // number of nodes
48    int k;                       // maximum number of edges we are allowed to boost
49    vector<vector<int>> edges;   // edge list: {u, v, strength, mustInclude}
50
51    // Check whether a connected graph can be formed such that every used edge
52    // has effective stability >= lim.
53    // - An edge with strength s can be used directly if s >= lim.
54    // - An edge can be "boosted" (doubling its strength) if s * 2 >= lim,
55    //   but we may boost at most k edges in total.
56    bool check(int lim) {
57        UnionFind uf(n);
58
59        // First pass: connect with edges that already meet the threshold for free
60        for (auto& e : edges) {
61            int u = e[0], v = e[1], s = e[2];
62            if (s >= lim) {
63                uf.unite(u, v);
64            }
65        }
66
67        // Second pass: use boosted edges (limited by remaining budget) to
68        // connect components that are still separated.
69        int remaining = k;
70        for (auto& e : edges) {
71            int u = e[0], v = e[1], s = e[2];
72            if (s * 2 >= lim && remaining > 0) {
73                if (uf.unite(u, v)) {
74                    --remaining;
75                }
76            }
77        }
78
79        // The graph is feasible if everything collapses into one component
80        return uf.count == 1;
81    }
82
83    int maxStability(int n, vector<vector<int>>& edges, int k) {
84        this->n = n;
85        this->edges = edges;
86        this->k = k;
87
88        UnionFind uf(n);
89        int minMustStrength = 1e6;   // smallest strength among mandatory edges
90
91        // Process all mandatory edges. They must all be included, so:
92        // - Track the minimum strength among them (caps the achievable answer).
93        // - If two mandatory edges create a cycle, the configuration is invalid.
94        for (auto& e : edges) {
95            int u = e[0], v = e[1], s = e[2], mustInclude = e[3];
96            if (mustInclude) {
97                minMustStrength = min(minMustStrength, s);
98                if (!uf.unite(u, v)) {
99                    return -1;   // mandatory edges form a cycle -> impossible
100                }
101            }
102        }
103
104        // Add every remaining edge to test overall connectivity feasibility
105        for (auto& e : edges) {
106            uf.unite(e[0], e[1]);
107        }
108
109        // If the graph cannot be fully connected at all, no answer exists
110        if (uf.count > 1) {
111            return -1;
112        }
113
114        // Binary search on the answer (the maximum achievable minimum stability).
115        // The upper bound is minMustStrength because mandatory edges cannot be
116        // boosted and limit the threshold.
117        int left = 1, right = minMustStrength;
118        while (left < right) {
119            int mid = (left + right + 1) >> 1;
120            if (check(mid)) {
121                left = mid;       // mid is achievable, try for higher
122            } else {
123                right = mid - 1;  // mid too high, lower the bound
124            }
125        }
126
127        return left;
128    }
129};
130

1// Union-Find (Disjoint Set Union) global state
2let parent: number[]; // parent[i] points to the representative of i's set
3let rank: number[]; // rank/size used for union by size optimization
4let count: number; // number of disjoint connected components
5
6/**
7 * Initialize the Union-Find structure for n elements.
8 * Each element starts as its own parent (separate component).
9 */
10function init(n: number): void {
11    parent = Array.from({ length: n }, (_, i) => i);
12    rank = new Array(n).fill(1);
13    count = n;
14}
15
16/**
17 * Find the representative (root) of the set containing x.
18 * Uses path compression to flatten the tree for efficiency.
19 */
20function find(x: number): number {
21    if (parent[x] !== x) {
22        parent[x] = find(parent[x]);
23    }
24    return parent[x];
25}
26
27/**
28 * Merge the sets containing a and b using union by size.
29 * Returns true if a merge happened, false if they were already connected.
30 */
31function union(a: number, b: number): boolean {
32    const rootA = find(a);
33    const rootB = find(b);
34    if (rootA === rootB) return false;
35
36    // Attach the smaller tree under the larger tree
37    if (rank[rootA] > rank[rootB]) {
38        parent[rootB] = rootA;
39        rank[rootA] += rank[rootB];
40    } else {
41        parent[rootA] = rootB;
42        rank[rootB] += rank[rootA];
43    }
44
45    count--;
46    return true;
47}
48
49// Global problem inputs shared with the check function
50let nodeCount: number; // total number of nodes
51let edgeList: number[][]; // list of edges: [u, v, strength, must]
52let maxUpgrades: number; // maximum number of edges allowed to be upgraded (x2)
53
54/**
55 * Verify whether the graph can be fully connected (single component)
56 * while every used edge meets the strength threshold `limit`.
57 *
58 * Step 1: Add all edges whose original strength already satisfies `limit`.
59 * Step 2: Use remaining upgrade budget on edges that satisfy `limit`
60 *         only after doubling their strength (strength * 2 >= limit).
61 * Returns true if the whole graph becomes one connected component.
62 */
63function check(limit: number): boolean {
64    init(nodeCount);
65
66    // Phase 1: edges that already meet the threshold without upgrading
67    for (const [u, v, strength] of edgeList) {
68        if (strength >= limit) {
69            union(u, v);
70        }
71    }
72
73    // Phase 2: spend upgrade budget on edges that qualify after doubling
74    let remaining = maxUpgrades;
75    for (const [u, v, strength] of edgeList) {
76        if (strength * 2 >= limit && remaining > 0) {
77            if (union(u, v)) {
78                remaining--;
79            }
80        }
81    }
82
83    return count === 1;
84}
85
86/**
87 * Compute the maximum achievable stability of the network.
88 *
89 * The stability is defined as the minimum edge strength across all used
90 * edges. We can optionally double the strength of up to `k` non-mandatory
91 * edges. Mandatory edges (must === 1) must always be included.
92 *
93 * Approach:
94 * 1. Connect all mandatory edges first; if any forms a cycle, the
95 *    configuration is invalid (returns -1).
96 * 2. Track the minimum strength among mandatory edges as the upper bound,
97 *    since the answer can never exceed the weakest mandatory edge.
98 * 3. Verify the full graph is connectable using all edges; otherwise -1.
99 * 4. Binary search on the answer (the threshold strength), using `check`
100 *    to test feasibility for each candidate value.
101 */
102function maxStability(n: number, edges: number[][], k: number): number {
103    nodeCount = n;
104    edgeList = edges;
105    maxUpgrades = k;
106
107    init(n);
108    let minMandatory = 1e6; // upper bound of the answer
109
110    // Step 1 & 2: add mandatory edges and track their minimum strength
111    for (const [u, v, strength, must] of edges) {
112        if (must) {
113            minMandatory = Math.min(minMandatory, strength);
114            if (!union(u, v)) return -1; // mandatory edges form a cycle
115        }
116    }
117
118    // Step 3: ensure the graph can be fully connected using every edge
119    for (const [u, v] of edges) {
120        union(u, v);
121    }
122
123    if (count > 1) return -1; // graph cannot be fully connected
124
125    // Step 4: binary search for the largest feasible threshold
126    let left = 1;
127    let right = minMandatory;
128
129    while (left < right) {
130        const mid = (left + right + 1) >> 1;
131        if (check(mid)) {
132            left = mid; // mid is feasible, try a higher threshold
133        } else {
134            right = mid - 1; // mid is too high, lower the threshold
135        }
136    }
137
138    return left;
139}
140