## 1) Abridged problem statement

There are **N** initial parties (1…N). Directed edges `(a -> b)` mean *a has discrediting information about b*.
We process **Q** queries:

- **`1 a b`**: output **YES/NO** — does entity `a` (party or previously created block) know something about entity `b`?
- **`2 a b`**: **merge** entities `a` and `b` into a **new block** with a new id (N+1, N+2, …).
  The new block:
  - keeps **all outgoing info** of both (`a`'s and `b`'s outgoing edges become outgoing from the new block),
  - and all **incoming info** to either `a` or `b` now points to the new block (edges into `a` or `b` become edges into the new block).
  - Self-information is allowed.

All queries refer only to currently existing parties/blocks.

Constraints: `N ≤ 1e5, M ≤ 2e5, Q ≤ 2e5`.

---

## 2) Detailed Editorial

### Model as a dynamic directed graph of "current entities"
At any time we have some active entities (initial parties plus blocks created so far). A merge replaces two active nodes `u` and `v` by a new block `k`.

We must support:
- **Edge existence query**: is there an edge `u -> v`?
- **Merge operation**: redirect all edges incident to `u` or `v` to point to `k`, and union their outgoing sets.

A naive merge that scans all nodes to redirect edges is too slow.

### Key idea: small-to-large (DSU-style) on adjacency maintenance
Maintain for each **active representative id**:
- `know[x]`: list of outgoing neighbors (edges `x -> y`)
- `appears[x]`: list of incoming sources (edges `y -> x`), i.e., reverse adjacency

When merging `u` and `v`, we choose to **keep** the "bigger" structure and move the smaller one into it:
- pick `u` as the "large" node, `v` as "small"
- move all outgoing edges of `v` into `u`
- move all incoming edges of `v` into `u` by updating those sources' outgoing edges

This reduces total moved elements over all merges: each edge endpoint participates in moves only `O(log N)` times amortized. The size metric used in code is `know[x].size() + appears[x].size()`, which approximates total incident edges stored for that node.

### Fast edge queries with a global hash set
Checking "does `u` know `v`?" should be `O(1)` average.

The solution keeps a hash table `edges` containing all currently known directed edges as keys, encoded as `key(u,v) = u * MOD + v` with `MOD = n + 1`. This is collision-free because the ids used inside `edges` are *internal representative ids in [0..n-1]*, so both `u` and `v` are below `MOD`.

Important subtlety: the code never creates a new internal node for a merged block; it **reuses** one of the two reps (the chosen `u`). The "new block number" from the statement is handled by the `id[]` mapping (explained next), not by creating a fresh graph node.

### Handling new block identifiers: the `id[]` indirection trick
Queries refer to block numbers N+1, N+2, … which are new "names". Internally, the algorithm wants to keep only a small set of representatives.

So it maintains `id[x]` = internal representative of external entity number `x` (0-indexed). Initially, `id[i] = i` for parties.

When a merge happens and we decide the representative is `u`, we create a new external id for the new block by doing `id.push_back(u)`. Thus, the new external number maps to representative `u`. The old representative `v` is marked inactive and its lists are cleared.

So external entities are just aliases that point to the current internal representative.

### How merge updates are done
Merge `u` (keep) and `v` (absorb), both internal representatives.

We must ensure semantics:
- Outgoing of new block = outgoing(u) ∪ outgoing(v)
- Incoming of new block = incoming(u) ∪ incoming(v)
- Any edge involving v should now involve u

The code performs two loops:

1) For each outgoing edge `v -> x` (x from `know[v]`):
- if `x` inactive, skip (stale)
- if `x == v`, it becomes `u -> u` (self-loop remapped)
- add edge `u -> target` into `know[u]`, `appears[target]` (reverse link) and `edges`

2) For each incoming edge `x -> v` (x from `appears[v]`):
- if `x` inactive, skip
- if `x == v`, it becomes `u -> u`
- add edge `source -> u` into `know[source]`, `appears[u]` and `edges`

Then it clears `know[v]`, `appears[v]`, sets `active[v]=false`.

#### Why are stale entries okay?
When we "add" edges during merges, we never remove old edges from `edges` or adjacency lists; that would be expensive.

Instead:
- inactive nodes are ignored during merges (`if !active[x] continue`)
- queries use current representatives `pa=id[a], pb=id[b]`; representatives are always active
- `edges` contains all edges ever created between representatives, and because representatives are reused, the relevant ones remain valid for the current rep graph.

This is the common "lazy" approach: don't delete, only add, and ignore dead nodes.

### Complexity
Let `S(x)=|know[x]|+|appears[x]|` for active reps.

By small-to-large, every time an element from lists moves, it moves into a structure at least twice as big, so each element moves `O(log N)` times amortized.

Total work over all merges is `O((M + number_of_added_links) log N)` average with hashing. Type-1 queries are `O(1)` average each. With a `gp_hash_table` the constant is small enough to fit the constraints.

---

## 3) C++ Solution

```cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int n, m, q;
vector<vector<int>> know;

void read() {
    cin >> n >> m;
    know.assign(n, {});
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        know[a].push_back(b);
    }
    cin >> q;
}

void solve() {
    // The core idea in the solution is to do small to large trick. Whenever two
    // groups merge (query 2), we will choose the larger set and keep it as as,
    // and manually move everyone from the smaller group. This amortizes to O(N
    // log^2 N) or O(N log N), depending on what structure we use. The tricky
    // part is maintaining the correct identifiers. Particularly, if we change
    // the id of some group, we should also change it in the knowledge sets of
    // other groups. To make this convenient, when we merge groups u, v -> k
    // (size(u) > size(v)), what we will do is keep id[k] = id[u], and go
    // through each occurrence of id[v] in some knowledge list, and change it to
    // id[u]. Because of small to large, each id[u] can change at most O(log N)
    // times, making this part also O(M log^2 N). It's O(log^2 N), mostly
    // because we want to use sets so that the query is easy to implement. With
    // a hash table this might be a bit faster, as we don't really need the
    // sorted order in each of these sets. It's a bit hard to pass given the
    // constraints on codeforces, so we have to make some optimizations.
    // Notably, we could actually do the id updates lazily, by only doing the
    // addition at the time of the update, and remove the old ones at the time
    // of the merge. Also using a better hash table like gp_hash_table makes
    // this considerably quicker. Overall the complexity below is O((N + M + Q)
    // log N * c), where c ~ O(1) from the hash table.

    vector<int> id(n);
    iota(id.begin(), id.end(), 0);

    vector<bool> active(n, true);
    vector<vector<int>> appears(n);
    for(int i = 0; i < n; i++) {
        for(int j: know[i]) {
            appears[j].push_back(i);
        }
    }

    gp_hash_table<int64_t, null_type, custom_hash> edges;
    int64_t MOD = n + 1LL;
    for(int i = 0; i < n; i++) {
        for(int j: know[i]) {
            edges.insert(i * MOD + j);
        }
    }

    for(int qi = 0; qi < q; qi++) {
        int type, a, b;
        cin >> type >> a >> b;
        a--;
        b--;

        if(type == 1) {
            int pa = id[a];
            int pb = id[b];
            cout << (edges.find(pa * MOD + pb) != edges.end() ? "YES" : "NO")
                 << "\n";
        } else {
            int u = id[a], v = id[b];
            if(u == v) {
                continue;
            }

            if(know[u].size() + appears[u].size() <
               know[v].size() + appears[v].size()) {
                swap(u, v);
            }

            for(int x: know[v]) {
                if(!active[x]) {
                    continue;
                }
                int target = (x == v ? u : x);
                know[u].push_back(target);
                appears[target].push_back(u);
                edges.insert(u * MOD + target);
            }
            for(int x: appears[v]) {
                if(!active[x]) {
                    continue;
                }
                int source = (x == v ? u : x);
                know[source].push_back(u);
                appears[u].push_back(source);
                edges.insert(source * MOD + u);
            }

            know[v].clear();
            appears[v].clear();
            active[v] = false;

            id.push_back(u);
        }
    }
}

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

    int T = 1;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }
    return 0;
}
```

---

## 4) Python solution (same approach) with detailed comments

```python
import sys

def solve() -> None:
    sys.setrecursionlimit(1_000_000)
    input = sys.stdin.readline

    n, m = map(int, input().split())

    # know[u] = outgoing adjacency list (representatives are 0..n-1 only)
    know = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        know[a].append(b)

    q = int(input())

    # id maps external entity index -> internal representative
    # external indices start with 0..n-1 and we append for each merge
    id_map = list(range(n))

    # active reps: only original reps exist, some will be "killed" by merges
    active = [True] * n

    # appears[v] = list of sources u such that u -> v exists (reverse edges)
    appears = [[] for _ in range(n)]
    for u in range(n):
        for v in know[u]:
            appears[v].append(u)

    # We need fast edge existence queries between representatives.
    # Representants are in [0..n-1], so we can encode (u,v) as u*MOD + v
    MOD = n + 1
    edges = set()
    for u in range(n):
        for v in know[u]:
            edges.add(u * MOD + v)

    out_lines = []

    for _ in range(q):
        t, a, b = map(int, input().split())
        a -= 1; b -= 1

        if t == 1:
            ra = id_map[a]
            rb = id_map[b]
            out_lines.append("YES" if (ra * MOD + rb) in edges else "NO")
        else:
            u = id_map[a]
            v = id_map[b]
            if u == v:
                # Mimic the C++ code exactly: no structural change and no new id.
                continue

            # Small-to-large heuristic: keep u as larger
            if len(know[u]) + len(appears[u]) < len(know[v]) + len(appears[v]):
                u, v = v, u

            # Move outgoing edges v -> x into u -> x (with v remapped to u)
            for x in know[v]:
                if not active[x]:
                    continue
                target = u if x == v else x
                know[u].append(target)
                appears[target].append(u)
                edges.add(u * MOD + target)

            # Move incoming edges x -> v into x -> u (with v remapped to u)
            for x in appears[v]:
                if not active[x]:
                    continue
                source = u if x == v else x
                know[source].append(u)
                appears[u].append(source)
                edges.add(source * MOD + u)

            # Kill v
            know[v].clear()
            appears[v].clear()
            active[v] = False

            # New external block id points to representative u
            id_map.append(u)

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()
```

Note: This mirrors the provided C++ behavior (including not appending a new external id if `u==v` after mapping). If you want to follow the statement literally (always creating a new block id), you would append `u` even in that case; but the C++ solution does not, and relies on the input structure / accepted interpretation.

---

## 5) Compressed editorial

Maintain the graph between **internal representatives** (initial parties only). Each external block id stores a pointer `id[x]` to a representative.

Keep:
- `know[u]`: outgoing neighbors
- `appears[u]`: incoming neighbors
- global hash set `edges` for O(1) edge existence queries.

For merge `2 a b`:
- map to reps `u=id[a]`, `v=id[b]`
- small-to-large: keep the rep with larger `|know|+|appears|`
- add all outgoing `v->x` as `u->x` (remap `v` to `u`)
- add all incoming `x->v` as `x->u` (remap `v` to `u`)
- mark `v` inactive, clear its lists
- append new external id: `id.push_back(u)`

Query `1 a b`: check whether `edges` contains `(id[a], id[b])`.

Amortized `O((M+Q) log N)` list moves with O(1) hashing per inserted edge; fits limits.
