/tmp/solutions/build/unionfind-main.cpp:
    1|       |#include <common.h>
    2|       |prelude;
    3|       |
    4|       |namespace {
    5|       |
    6|       |int pa[200000];
    7|       |
    8|  98.9k|def find(int u) -> int {
    9|  98.9k|  int w = pa[u], v;
   10|  98.9k|  if (w < 0) return u;
                           ^13.8k
  ------------------
  |  Branch (10:7): [True: 14.04%, False: 85.96%]
  ------------------
   11|  89.5k|  while (pa[w] >= 0) w = pa[w];
                ^85.0k             ^4.52k
  ------------------
  |  Branch (11:10): [True: 5.05%, False: 94.95%]
  ------------------
   12|  89.5k|  while (pa[u] != w) v = u, u = pa[u], pa[v] = w;
                                   ^4.52k
  ------------------
  |  Branch (12:10): [True: 5.05%, False: 94.95%]
  ------------------
   13|  85.0k|  return w;
   14|  98.9k|};
   15|       |
   16|       |} // namespace
   17|       |
   18|      1|int main() {
   19|      1|  rd rd;
   20|      1|  wt wt;
   21|      1|  int n = rd.uh();
   22|      1|  int q = rd.uh();
   23|      1|  std::memset(pa, -1, 4 * n);
   24|  49.4k|  while (q--) {
  ------------------
  |  Branch (24:10): [True: 100.00%, False: 0.00%]
  ------------------
   25|  49.4k|    let t = rd.u1();
   26|  49.4k|    let u = find(rd.uh());
   27|  49.4k|    let v = find(rd.uh());
   28|  49.4k|    if (t == 0 && u != v) {
                                ^24.9k
  ------------------
  |  Branch (28:9): [True: 50.39%, False: 49.61%]
  |  Branch (28:19): [True: 23.36%, False: 76.64%]
  ------------------
   29|  5.82k|      if (pa[u] < pa[v])
  ------------------
  |  Branch (29:11): [True: 34.56%, False: 65.44%]
  ------------------
   30|  2.01k|        pa[v] = u;
   31|  3.81k|      else if (pa[v] < pa[u])
  ------------------
  |  Branch (31:16): [True: 52.23%, False: 47.77%]
  ------------------
   32|  1.99k|        pa[u] = v;
   33|  1.82k|      else
   34|  1.82k|        pa[u] = v, --pa[v];
   35|  5.82k|    }
   36|  49.4k|    if (t == 1) {
  ------------------
  |  Branch (36:9): [True: 49.61%, False: 50.39%]
  ------------------
   37|  24.5k|      wt.u1(u == v);
   38|  24.5k|    }
   39|  49.4k|  }
   40|      1|  return 0;
   41|      1|}