1
impl Solution {
2
  pub fn max_num_edges_to_remove(n: i32, edges: Vec<Vec<i32>>) -> i32 {
3
    let mut alice: Vec<_> = (0..=n as usize).collect();
4
    let mut bob: Vec<_> = (0..=n as usize).collect();
5

6
    fn uf_find(i: usize, uf: &mut [usize]) -> usize {
7
      if uf[i] != i {
8
        uf[i] = uf_find(uf[i], uf);
9
      }
10
      uf[i]
11
    }
12
    fn uf_union(i: usize, j: usize, uf: &mut [usize]) -> bool {
13
      let i = uf_find(i, uf);
14
      let j = uf_find(j, uf);
15
      if i == j {
16
        false
17
      } else {
18
        uf[i] = j;
19
        true
20
      }
21
    }
22

23
    let mut ret = 0;
24
    let mut a_count = 1;
25
    let mut b_count = 1;
26
    for edge in &edges {
27
      if edge[0] == 3 {
28
        let a_change = uf_union(edge[1] as usize, edge[2] as usize, &mut alice);
29
        let b_change = uf_union(edge[1] as usize, edge[2] as usize, &mut bob);
30
        match (a_change, b_change) {
31
          (true, true) => {
32
            a_count += 1;
33
            b_count += 1;
34
          }
35
          (true, false) => {
36
            a_count += 1;
37
          }
38
          (false, true) => {
39
            b_count += 1;
40
          }
41
          (false, false) => {
42
            ret += 1;
43
          }
44
        }
45
      }
46
    }
47
    for edge in edges {
48
      if edge[0] == 1 {
49
        if uf_union(edge[1] as usize, edge[2] as usize, &mut alice) {
50
          a_count += 1;
51
        } else {
52
          ret += 1;
53
        }
54
      } else if edge[0] == 2 {
55
        if uf_union(edge[1] as usize, edge[2] as usize, &mut bob) {
56
          b_count += 1;
57
        } else {
58
          ret += 1;
59
        }
60
      }
61
    }
62

63
    if a_count < n || b_count < n {
64
      -1
65
    } else {
66
      ret
67
    }
68
  }
69
}