BOJ 17722 - Road Development 링크
(2023.06.20 기준 D5)

문제

두 도시를 잇는 도로가 없이 도시 N개가 있다. Q개의 교통 개선 게획이 수립이 되었는데, 일부는 실행되고 나머지는 실행되지 않았다. 이 계획은 T A B 형태의 쿼리로 주어지는데 다음과 같다.

1. T = 1
   계획이 실행이 되었다. A와 B가 이미 도로로 이어져 있다면, A와 B의 최단 경로에 존재하는 비포장 도로를 포장한다.
   A와 B가 도로로 이어지지 않았다면 A와 B를 비포장 도로로 잇는다.
   
   
2. T = 2
   계획이 실행되지 않았다. A와 B가 도로로 이어져 있다면, A와 B의 최단 경로에 존재하는 비포장 도로의 개수를 출력한다.
   A와 B가 도로로 이어지지 않았다면 -1을 출력한다.

이에 맞게 Q개의 계획(쿼리)를 알맞게 처리

알고리즘

이어졌는지는 분리 집합, 구간 내 업데이트 및 쿼리는 세그먼트 트리(lazyprop), 이를 트리에서 쓰기 위해선 HLD, 그리고 오프라인 쿼리. 참 많다.

풀이

쿼리를 보면 도로가 이어져 있다면 더 이을 필요가 없다. 이는 결국 사이클이 없는 트리를 구성해가자는 뜻이 된다.

이어진 상태는 일단 분리 집합을 사용하자.

쿼리에서 T = 2인 쿼리는 실제로 간선을 잇지 않는다. 그러므로 일단 쿼리를 전부 받아두고 T = 1인 쿼리의 간선만 사용하여 HLD를 만들자. 물론, 분리 집합을 사용하여 이미 이어진 두 도시 사이의 간선은 사용하지 않아야 한다. 이렇게 쿼리를 오프라인 쿼리로 처리하자.

쿼리에서 T = 2인 쿼리에서 출력해야 하는 것은 비포장 도로의 개수이다.
그러므로 구간합 세그먼트 트리의 리프 노드의 초기 값을 1로 잡고 구간 내 포장. 즉, 구간 내 업데이트는 노드 값을 0으로 만드는 작업을 하면 된다.

HLD를 완성하였고, 초기화된 세그먼트 트리와 분리 집합이 있다면 이제 쿼리를 처리할 차례다.
오프라인 쿼리에서 사용했던 분리 집합은, 이제 모든 쿼리를 다시 처음부터 차례대로 처리해야 하기 때문에 다시 초기화하자.

T = 1인 쿼리는 이어져 있다면(A와 B의 분리 집합 부모가 같다면) 비포장 도로를 포장(구간 [A, B]를 전부 0으로 업데이트)하자.
이어지지 않았다면(A와 B의 분리 집합 부모가 다르다면) A와 B를 잇자(A와 B를 union).

T = 2인 쿼리는 이어져 있다면(A와 B의 분리 집합 부모가 같다면) 비포장 도로의 개수(구간 [A, B] 쿼리)를 출력하자.
이어지지 않았다면(A와 B의 분리 집합 부모가 다르다면) -1을 출력하자.

코드 (2023.07.03 수정)

• C++

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int, int, int> tiii;

const int MAXN = 100000, MAXH = 1 << (int)ceil(log2(MAXN) + 1);

int N, Q, T, A, B;
vector<tiii> queries;

// 분리 집합
struct DS{
    int pa[MAXN];

    void init();

    int find(int u){
        if (pa[u] != u) pa[u] = find(pa[u]);
        return pa[u];
    }

    void merge(int u, int v){
        u = find(u); v = find(v);

        if (u < v) pa[v] = u;
        else pa[u] = v;
    }
}ds;

// 세그먼트 트리
struct ST{
    int tree[MAXH], lazy[MAXH];

    void init(int nd, int st, int en){
        if (st == en) tree[nd] = 1;
        else{
            int mid = (st + en) >> 1;
            init(nd << 1, st, mid);
            init(nd << 1 | 1, mid + 1, en);
            tree[nd] = tree[nd << 1] + tree[nd << 1 | 1];
        }
    }

    void init();

    void update_lazy(int nd, int st, int en){
        if (lazy[nd]){
            tree[nd] = 0;
            if (st != en) lazy[nd << 1] = lazy[nd << 1 | 1] = 1;
            lazy[nd] = 0;
        }
    }

    void update(int nd, int st, int en, int l, int r){
        update_lazy(nd, st, en);
        if (r < st || en < l) return;
        if (l <= st && en <= r){
            tree[nd] = 0;
            if (st != en) lazy[nd << 1] = lazy[nd << 1 | 1] = 1;
            return;
        }
        int mid = (st + en) >> 1;
        update(nd << 1, st, mid, l, r);
        update(nd << 1 | 1, mid + 1, en, l, r);
        tree[nd] = tree[nd << 1] + tree[nd << 1 | 1];
    }

    int query(int nd, int st, int en, int l, int r){
        update_lazy(nd, st, en);
        if (r < st || en < l) return 0;
        if (l <= st && en <= r) return tree[nd];
        int mid = (st + en) >> 1;
        return query(nd << 1, st, mid, l, r) + query(nd << 1 | 1, mid + 1, en, l, r);
    }
}st;

// heavy-light 분할
struct HLD{
    int sz[MAXN], pa[MAXN], lv[MAXN], in[MAXN], out[MAXN], head[MAXN], idx;
    vector<int> graph[MAXN];

    void init();

    int _dfs(int here){
        sz[here] = 1;
        for (int i = 0, gsz = graph[here].size(); i < gsz; i++){
            int there = graph[here][i];
            if (pa[here] == there) continue;
            pa[there] = here;
            lv[there] = lv[here] + 1;
            sz[here] += _dfs(there);
            if (sz[graph[here][0]] < sz[there]) swap(graph[here][0], graph[here][i]);
        }

        return sz[here];
    }

    void _hld(int here){
        in[here] = ++idx;

        for (auto there: graph[here]){
            if (pa[here] == there) continue;
            if (graph[here][0] == there) head[there] = head[here];
            else head[there] = there;
            _hld(there);
        }

        out[here] = idx;
    }

    void update(int u, int v){
        while (head[u] != head[v]){
            if (lv[head[u]] < lv[head[v]]) swap(u, v);
            st.update(1, 0, N - 1, in[head[u]], in[u]);
            u = pa[head[u]];
        }

        if (in[u] > in[v]) swap(u, v);
        st.update(1, 0, N - 1, in[u] + 1, in[v]);
    }

    int query(int u, int v){
        int result = 0;

        while (head[u] != head[v]){
            if (lv[head[u]] < lv[head[v]]) swap(u, v);
            result += st.query(1, 0, N - 1, in[head[u]], in[u]);
            u = pa[head[u]];
        }

        if (in[u] > in[v]) swap(u, v);
        result += st.query(1, 0, N - 1, in[u] + 1, in[v]);

        return result;
    }
}hld;

void DS::init(){
    iota(pa, pa + N, 0);
}

void ST::init(){
    fill(tree, tree + MAXH, 0);
    fill(lazy, lazy + MAXH, 0);
    init(1, 0, N - 1);
}

void HLD::init(){
    fill(sz, sz + N, 0);
    fill(pa, pa + N, 0);
    fill(lv, lv + N, 0);
    fill(in, in + N, 0);
    fill(out, out + N, 0);
    fill(head, head + N, 0);
    idx = -1;

    _dfs(0); _hld(0);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> Q;

    // 분리 집합, 세그먼트 트리 초기화
    ds.init();
    st.init();

    // 쿼리 저장 및 T = 1인 쿼리의 간선을 그래프에 추가
    while (Q--){
        cin >> T >> A >> B;
        queries.push_back({T, --A, --B});

        if (T == 1){
            if (ds.find(A) != ds.find(B)){
                ds.merge(A, B);
                hld.graph[A].push_back(B);
                hld.graph[B].push_back(A);
            }
        }
    }

    // 루트인 0번과 이어지지 않은 정점을 이어주기
    for (int i = 1; i < N; i++) if (ds.find(i)){
        ds.merge(0, i);
        hld.graph[0].push_back(i);
        hld.graph[i].push_back(0);
    }

    // HLD 완성
    hld.init();

    // 분리 집합 다시 초기화
    ds.init();

    for (auto [T, A, B]: queries){
        if (T == 1){
            if (ds.find(A) == ds.find(B)) // 이어져 있다면 포장
                hld.update(A, B);
            else // 이어지지 않았다면 잇기
                ds.merge(A, B);
        }
        else{
            if (ds.find(A) == ds.find(B)) // 이어져 있다면 포장되지 앟은 길의 수 출력
                cout << hld.query(A, B) << '\n';
            else // 이어지지 않았다면 -1 출력
                cout << -1 << '\n';
        }
    }
}

• Python (TLE)

import sys; input = sys.stdin.readline
sys.setrecursionlimit(500000)
from math import ceil, log2

# 분리 집합
class DS:
    def __init__(self, N):
        self.pa = [i for i in range(N)]

    def find(self, u):
        if self.pa[u] != u:
            self.pa[u] = self.find(self.pa[u])
        return self.pa[u]

    def union(self, u, v):
        u = self.find(u)
        v = self.find(v)

        if u < v:
            self.pa[v] = u
        else:
            self.pa[u] = v

# 세그먼트 트리
class ST:
    def __init__(self, N):
        H = 1 << ceil(log2(N) + 1)
        self.tree = [0] * H
        self.lazy = [0] * H
        self._init(1, 0, N - 1)

    def _init(self, nd, st, en):
        if st == en:
            self.tree[nd] = 1
        else:
            mid = (st + en) >> 1
            self._init(nd << 1, st, mid)
            self._init(nd << 1 | 1, mid + 1, en)
            self.tree[nd] = self.tree[nd << 1] + self.tree[nd << 1 | 1]

    def _update_lazy(self, nd, st, en):
        if self.lazy[nd]:
            self.tree[nd] = 0
            if st != en:
                self.lazy[nd << 1] = self.lazy[nd << 1 | 1] = 1
            self.lazy[nd] = 0

    def update(self, nd, st, en, l, r):
        self._update_lazy(nd, st, en)
        if r < st or en < l:
            return
        if l <= st and en <= r:
            self.tree[nd] = 0
            if st != en:
                self.lazy[nd << 1] = self.lazy[nd << 1 | 1] = 1
            return
        mid = (st + en) >> 1
        self.update(nd << 1, st, mid, l, r)
        self.update(nd << 1 | 1, mid + 1, en, l, r)
        self.tree[nd] = self.tree[nd << 1] + self.tree[nd << 1 | 1]

    def query(self, nd, st, en, l, r):
        self._update_lazy(nd, st, en)
        if r < st or en < l:
            return 0
        if l <= st and en <= r:
            return self.tree[nd]
        mid = (st + en) >> 1
        return self.query(nd << 1, st, mid, l, r) + self.query(nd << 1 | 1, mid + 1, en, l, r)

# heavy-light 분할
class HLD:
    def __init__(self, N):
        self.N = N
        self.graph = [[] for _ in range(self.N)]
        self.sz = [0] * self.N
        self.pa = [0] * self.N
        self.lv = [0] * self.N
        self.inn = [0] * self.N
        self.head = [0] * self.N
        self.idx = -1

    def init(self):
        self._dfs(0)
        self._hld(0)

    def _dfs(self, here):
        self.sz[here] = 1
        for i in range(len(self.graph[here])):
            there = self.graph[here][i]
            if self.pa[here] == there:
                continue
            self.pa[there] = here
            self.lv[there] = self.lv[here] + 1
            self.sz[here] += self._dfs(there)
            if self.sz[self.graph[here][0]] < self.sz[there]:
                self.graph[here][0], self.graph[here][i] = self.graph[here][i], self.graph[here][0]

        return self.sz[here]

    def _hld(self, here):
        self.idx += 1
        self.inn[here] = self.idx

        for there in self.graph[here]:
            if self.pa[here] == there:
                continue
            if self.graph[here][0] == there:
                self.head[there] = self.head[here]
            else:
                self.head[there] = there
            self._hld(there)

    def update(self, u, v):
        while self.head[u] != self.head[v]:
            if self.lv[self.head[u]] < self.lv[self.head[v]]:
                u, v = v, u
            st.update(1, 0, N - 1, self.inn[self.head[u]], self.inn[u])
            u = self.pa[self.head[u]]

        if self.inn[u] > self.inn[v]:
            u, v = v, u
        st.update(1, 0, N - 1, self.inn[u] + 1, self.inn[v])

    def query(self, u, v):
        result = 0

        while self.head[u] != self.head[v]:
            if self.lv[self.head[u]] < self.lv[self.head[v]]:
                u, v = v, u
            result += st.query(1, 0, N - 1, self.inn[self.head[u]], self.inn[u])
            u = self.pa[self.head[u]]

        if self.inn[u] > self.inn[v]:
            u, v = v, u
        result += st.query(1, 0, N - 1, self.inn[u] + 1, self.inn[v])

        return result

N, Q = map(int, input().split())

# 분리 집합, 세그먼트 트리 초기화 및 HLD 생성
ds = DS(N)
st = ST(N)
hld = HLD(N)

# 쿼리 저장 및 T = 1인 쿼리의 간선을 그래프에 추가
queries = [tuple(map(int, input().split())) for _ in range(Q)]
for T, A, B in queries:
    if T == 1:
        A -= 1; B -= 1
        if ds.find(A) != ds.find(B):
            ds.union(A, B)
            hld.graph[A].append(B)
            hld.graph[B].append(A)

# 루트인 0번과 이어지지 않은 정점을 이어주기
for i in range(1, N):
    if ds.find(i):
        ds.union(0, i)
        hld.graph[0].append(i)
        hld.graph[i].append(0)

# HLD 완성
hld.init()

# 분리 집합 다시 초기화
ds.pa = [i for i in range(N)]

for T, A, B in queries:
    A -= 1; B -= 1
    if T == 1:
        if ds.find(A) == ds.find(B): # 이어져 있다면 포장
            hld.update(A, B)
        else: # 이어지지 않았다면 잇기
            ds.union(A, B)
    else:
        if ds.find(A) == ds.find(B): # 이어져 있다면 포장되지 앟은 길의 수 출력
            print(hld.query(A, B))
        else: # 이어지지 않았다면 -1 출력
            print(-1)

코드 (수정 전)

• C++

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int, int, int> tiii;

const int MAXN = 100000, MAXH = 1 << (int)ceil(log2(MAXN) + 1);

int N, Q, T, A, B;
vector<tiii> queries;

// 분리 집합
struct DS{
    int pa[MAXN];

    void init(int N){
        iota(pa, pa + N, 0);
    }

    int find(int u){
        if (pa[u] != u) pa[u] = find(pa[u]);
        return pa[u];
    }

    void merge(int u, int v){
        u = find(u); v = find(v);

        if (u < v) pa[v] = u;
        else pa[u] = v;
    }
}ds;

// 세그먼트 트리
struct ST{
    int tree[MAXH], lazy[MAXH];

    void init(int nd, int st, int en){
        if (st == en) tree[nd] = 1;
        else{
            int mid = (st + en) >> 1;
            init(nd << 1, st, mid);
            init(nd << 1 | 1, mid + 1, en);
            tree[nd] = tree[nd << 1] + tree[nd << 1 | 1];
        }
    }

    void init(int N){
        init(1, 0, N - 1);
    }

    void update_lazy(int nd, int st, int en){
        if (lazy[nd]){
            tree[nd] = 0;
            if (st != en) lazy[nd << 1] = lazy[nd << 1 | 1] = 1;
            lazy[nd] = 0;
        }
    }

    void update(int nd, int st, int en, int l, int r){
        update_lazy(nd, st, en);
        if (r < st || en < l) return;
        if (l <= st && en <= r){
            tree[nd] = 0;
            if (st != en) lazy[nd << 1] = lazy[nd << 1 | 1] = 1;
            return;
        }
        int mid = (st + en) >> 1;
        update(nd << 1, st, mid, l, r);
        update(nd << 1 | 1, mid + 1, en, l, r);
        tree[nd] = tree[nd << 1] + tree[nd << 1 | 1];
    }

    int query(int nd, int st, int en, int l, int r){
        update_lazy(nd, st, en);
        if (r < st || en < l) return 0;
        if (l <= st && en <= r) return tree[nd];
        int mid = (st + en) >> 1;
        return query(nd << 1, st, mid, l, r) + query(nd << 1 | 1, mid + 1, en, l, r);
    }
}st;

// heavy-light 분할
struct HLD{
    int pa[MAXN], sz[MAXN], ids[MAXN], head[MAXN], idx;
    vector<int> graph[MAXN];

    int dfs(int here){
        sz[here] = 1;
        for (int i = 0, gsz = graph[here].size(); i < gsz; i++){
            int there = graph[here][i];
            if (pa[here] == there) continue;
            pa[there] = here;
            sz[here] += dfs(there);
            if (sz[graph[here][0]] < sz[there]) swap(graph[here][0], graph[here][i]);
        }

        return sz[here];
    }

    void hld(int here){
        ids[here] = idx++;

        for (auto there: graph[here]){
            if (pa[here] == there) continue;
            if (graph[here][0] == there) head[there] = head[here];
            else head[there] = there;
            hld(there);
        }
    }

    void init(int N){
        fill(pa, pa + N, 0);
        fill(sz, sz + N, 0);
        fill(ids, ids + N, 0);
        fill(head, head + N, 0);
        idx = 0;

        dfs(0); hld(0);
    }

    void update(int u, int v){
        while (head[u] != head[v]){
            if (sz[head[u]] > sz[head[v]]) swap(u, v);
            st.update(1, 0, N - 1, ids[head[u]], ids[u]);
            u = pa[head[u]];
        }
        if (ids[u] > ids[v]) swap(u, v);
        st.update(1, 0, N - 1, ids[u] + 1, ids[v]);
    }

    int query(int u, int v){
        int result = 0;

        while (head[u] != head[v]){
            if (sz[head[u]] > sz[head[v]]) swap(u, v);
            result += st.query(1, 0, N - 1, ids[head[u]], ids[u]);
            u = pa[head[u]];
        }
        if (ids[u] > ids[v]) swap(u, v);
        result += st.query(1, 0, N - 1, ids[u] + 1, ids[v]);

        return result;
    }
}hld;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> Q;

    // 분리 집합, 세그먼트 트리 초기화
    ds.init(N);
    st.init(N);

    // 쿼리 저장 및 T = 1인 쿼리의 간선을 그래프에 추가
    while (Q--){
        cin >> T >> A >> B;
        queries.push_back({T, --A, --B});

        if (T == 1){
            if (ds.find(A) != ds.find(B)){
                ds.merge(A, B);
                hld.graph[A].push_back(B);
                hld.graph[B].push_back(A);
            }
        }
    }

    // 루트인 0번과 이어지지 않은 정점을 이어주기
    for (int i = 1; i < N; i++) if (ds.find(i)){
        ds.merge(0, i);
        hld.graph[0].push_back(i);
        hld.graph[i].push_back(0);
    }

    // HLD 완성
    hld.init(N);

    // 분리 집합 다시 초기화
    ds.init(N);

    for (auto [T, A, B]: queries){
        if (T == 1){
            if (ds.find(A) == ds.find(B)) // 이어져 있다면 포장
                hld.update(A, B);
            else // 이어지지 않았다면 잇기
                ds.merge(A, B);
        }
        else{
            if (ds.find(A) == ds.find(B)) // 이어져 있다면 포장되지 앟은 길의 수 출력
                cout << hld.query(A, B) << '\n';
            else // 이어지지 않았다면 -1 출력
                cout << -1 << '\n';
        }
    }
}

• Python (TLE)

import sys; input = sys.stdin.readline
sys.setrecursionlimit(500000)
from math import ceil, log2

# 분리 집합
class DS:
    def __init__(self, N):
        self.pa = [i for i in range(N)]

    def find(self, u):
        if self.pa[u] != u:
            self.pa[u] = self.find(self.pa[u])
        return self.pa[u]

    def union(self, u, v):
        u = self.find(u)
        v = self.find(v)

        if u < v:
            self.pa[v] = u
        else:
            self.pa[u] = v

# 세그먼트 트리
class ST:
    def __init__(self, N):
        H = 1 << ceil(log2(N) + 1)
        self.tree = [0] * H
        self.lazy = [0] * H
        self._init(1, 0, N - 1)

    def _init(self, nd, st, en):
        if st == en:
            self.tree[nd] = 1
        else:
            mid = (st + en) >> 1
            self._init(nd << 1, st, mid)
            self._init(nd << 1 | 1, mid + 1, en)
            self.tree[nd] = self.tree[nd << 1] + self.tree[nd << 1 | 1]

    def _update_lazy(self, nd, st, en):
        if self.lazy[nd]:
            self.tree[nd] = 0
            if st != en:
                self.lazy[nd << 1] = self.lazy[nd << 1 | 1] = 1
            self.lazy[nd] = 0

    def update(self, nd, st, en, l, r):
        self._update_lazy(nd, st, en)
        if r < st or en < l:
            return
        if l <= st and en <= r:
            self.tree[nd] = 0
            if st != en:
                self.lazy[nd << 1] = self.lazy[nd << 1 | 1] = 1
            return
        mid = (st + en) >> 1
        self.update(nd << 1, st, mid, l, r)
        self.update(nd << 1 | 1, mid + 1, en, l, r)
        self.tree[nd] = self.tree[nd << 1] + self.tree[nd << 1 | 1]

    def query(self, nd, st, en, l, r):
        self._update_lazy(nd, st, en)
        if r < st or en < l:
            return 0
        if l <= st and en <= r:
            return self.tree[nd]
        mid = (st + en) >> 1
        return self.query(nd << 1, st, mid, l, r) + self.query(nd << 1 | 1, mid + 1, en, l, r)

# heavy-light 분할
class HLD:
    def __init__(self, N):
        self.graph = [[] for _ in range(N)]
        self.pa = [0] * N
        self.sz = [0] * N
        self.ids = [0] * N
        self.head = [0] * N
        self.idx = 0

    def _init(self):
        self._dfs(0)
        self._hld(0)

    def _dfs(self, here):
        self.sz[here] = 1;
        for i in range(len(self.graph[here])):
            there = self.graph[here][i]
            if self.pa[here] == there:
                continue
            self.pa[there] = here
            self.sz[here] += self._dfs(there)
            if self.sz[self.graph[here][0]] < self.sz[there]:
                self.graph[here][0], self.graph[here][i] = self.graph[here][i], self.graph[here][0]

        return self.sz[here]

    def _hld(self, here):
        self.ids[here] = self.idx
        self.idx += 1

        for there in self.graph[here]:
            if self.pa[here] == there:
                continue
            if self.graph[here][0] == there:
                self.head[there] = self.head[here]
            else:
                self.head[there] = there
            self._hld(there)

    def update(self, u, v):
        while self.head[u] != self.head[v]:
            if self.sz[self.head[u]] > self.sz[self.head[v]]:
                u, v = v, u
            st.update(1, 0, N - 1, self.ids[self.head[u]], self.ids[u])
            u = self.pa[self.head[u]]
        if self.ids[u] > self.ids[v]:
            u, v = v, u
        st.update(1, 0, N - 1, self.ids[u] + 1, self.ids[v])

    def query(self, u, v):
        result = 0

        while self.head[u] != self.head[v]:
            if self.sz[self.head[u]] > self.sz[self.head[v]]:
                u, v = v, u
            result += st.query(1, 0, N - 1, self.ids[self.head[u]], self.ids[u])
            u = self.pa[self.head[u]]
        if self.ids[u] > self.ids[v]:
            u, v = v, u
        result += st.query(1, 0, N - 1, self.ids[u] + 1, self.ids[v])

        return result

N, Q = map(int, input().split())

# 분리 집합, 세그먼트 트리 초기화 및 HLD 생성
ds = DS(N)
st = ST(N)
hld = HLD(N)

# 쿼리 저장 및 T = 1인 쿼리의 간선을 그래프에 추가
queries = [tuple(map(int, input().split())) for _ in range(Q)]
for T, A, B in queries:
    if T == 1:
        A -= 1; B -= 1
        if ds.find(A) != ds.find(B):
            ds.union(A, B)
            hld.graph[A].append(B)
            hld.graph[B].append(A)

# 루트인 0번과 이어지지 않은 정점을 이어주기
for i in range(1, N):
    if ds.find(i):
        ds.union(0, i)
        hld.graph[0].append(i)
        hld.graph[i].append(0)

# HLD 완성
hld._init()

# 분리 집합 다시 초기화
ds.pa = [i for i in range(N)]

for T, A, B in queries:
    A -= 1; B -= 1
    if T == 1:
        if ds.find(A) == ds.find(B): # 이어져 있다면 포장
            hld.update(A, B)
        else: # 이어지지 않았다면 잇기
            ds.union(A, B)
    else:
        if ds.find(A) == ds.find(B): # 이어져 있다면 포장되지 앟은 길의 수 출력
            print(hld.query(A, B))
        else: # 이어지지 않았다면 -1 출력
            print(-1)