<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

322. The Great Union
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The governments of Berland and Beerland announced the possible consolidation coming soon! Sounds unbelievable, but seems that the heads of the governments were able to come to an agreement. The only open issue is the old sore spot with the road network. Both countries have N cities, the cities in each country are numbered from 1 to N. Some pairs of cities are connected by bidirectional roads. There is exactly one way to get from one city to any other in each country. There are no roads between Berland and Beerland.

The decision was made to keep things clear for the drivers and to introduce a number of changes in the road networks. The essential requirement for the consolidation is the identity of the road networks in both countries. This mean that cities with numbers a and b are connected by a road in Berland if and only if the cities with the same numbers are connected by a road in Beerland.

The Autoroad Construction Multicultural team (ACM-team) was created to achieve this goal. During one month the team can perform construction and repair work in one country. During this monthly repair one road is added to the road network of the country, resulting in a cycle in the road network, so one road in the cycle should be closed. So as the result of the month's work, there is still exactly one way to get from one city to any other in each country.

What is the minimum number of months required to make the road networks of both countries identical? What is the plan of actions for the ACM-team in this case?

Input
The first line of the input file contains the integer number N (1 ≤ N ≤ 2000) — the number of cities in each country.

Each of the following N - 1 lines contains the description of the road in Berland given by the numbers of cities it connects. The following N - 1 lines contain the similar description of the roads in Beerland.

Output
Write the minimal amount of months Q ACM-team needs to finish the work to the first line of the output. In the following Q lines write the description of the work for each month. Work during each month is described by five numbers p, a1, b1, a2, b2, which means that the repairs should be held in Berland (if p = 1) or Beerland (if p = 2), the road a1, b1 should be added, and the road a2, b2 should be closed. If there are several solutions, choose any of them.

Example(s)
sample input
sample output
4
1 2
2 3
3 4
1 3
3 4
4 2
2
2 1 2 2 4
1 1 3 2 3

<|response|>
## 1) Abridged problem statement (concise)

You are given two **labeled trees** on the same vertex set `{1..N}`: Berland's tree and Beerland's tree (each has `N−1` undirected edges, connected, unique path between any two cities).

In one month you may modify **one** country's tree by:
- adding one edge `(a1, b1)` (creates exactly one cycle),
- removing one edge `(a2, b2)` **from that cycle**,

so the graph remains a tree.

Goal: make the two trees have **identical edge sets** (same labeled roads) using the **minimum** months, and output any optimal sequence of operations.

`N ≤ 2000`.

---

## 2) Key observations

1. Each country's road network is a **tree**. Adding one edge creates a **unique cycle**, and removing any edge on that cycle restores a tree.
2. Let `E1` be Berland edges and `E2` be Beerland edges. We need `E1 = E2` (exact equality, not isomorphism).
3. An operation can "swap" one edge of a tree: **add one edge, delete one edge** on the formed cycle.
4. Minimum number of operations is at least `|E1 \ E2|` (edges missing from Beerland but present in Berland), because each operation can introduce **at most one** such missing edge into Beerland.
5. We can achieve this lower bound by modifying **only Beerland**:
   - For each edge `(a,b) ∈ E1` missing in Beerland, add it to Beerland.
   - This forms a cycle consisting of the Beerland path from `a` to `b` plus `(a,b)`.
   - On that path, there must exist an edge that is **not** in Berland; otherwise Berland would contain the entire path plus `(a,b)` and would have a cycle (impossible because Berland is a tree).
   - Remove such a "bad" edge from Beerland. This replaces a wrong edge with a correct one.

Thus we can reach `E2 = E1` in exactly `|E1 \ E2|` months, which is optimal.

---

## 3) Full solution approach

We will transform Beerland's tree into Berland's tree. (The operation is symmetric, so it does not matter which country we modify; the code below applies all operations and reports them with `p = 2`.)

### Data structures
- `has1[u][v]`: whether edge `(u,v)` is in Berland (constant).
- `has2[u][v]`: whether edge `(u,v)` is currently in Beerland (changes as we operate).
- `adj2[u]`: adjacency list of the current Beerland tree for BFS path finding and modifications.
- list `input_edges1`: all edges of Berland to iterate over.

Since `N ≤ 2000`, adjacency matrices of size `(N+1)×(N+1)` are feasible.

### Algorithm
For every edge `(a,b)` in Berland:
1. If Beerland already has it (`has2[a][b] == true`), continue.
2. Find the unique path `P` between `a` and `b` in the current Beerland tree (BFS with parent pointers).
3. Scan edges along `P` to find the first edge `(x,y)` such that `has1[x][y] == false` (edge exists in Beerland's path but not in Berland). This edge must exist.
4. Perform one operation on Beerland:
   - add `(a,b)`
   - remove `(x,y)` (which lies on the cycle)

Record operation as: `2 a b x y`.

After all missing Berland edges are added, Beerland's edge set equals Berland's.
Number of operations equals the count of edges in `E1 \ E2` → minimal.

### Complexity
- At most `N-1` operations.
- Each operation does one BFS over a tree: `O(N)`.
- Total time: `O(N^2)` (fits easily).
- Memory: `O(N^2)` for matrices.

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

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;
};

int n;
vector<vector<bool>> has1, has2;
vector<vector<int>> adj2;
vector<pair<int, int>> input_edges1;

void read() {
    cin >> n;
    has1.assign(n + 1, vector<bool>(n + 1, false));
    has2.assign(n + 1, vector<bool>(n + 1, false));
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        has1[u][v] = has1[v][u] = true;
        input_edges1.emplace_back(u, v);
    }
    adj2.resize(n + 1);
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        has2[u][v] = has2[v][u] = true;
        adj2[u].push_back(v);
        adj2[v].push_back(u);
    }
}

vector<int> find_path(int start, int end) {
    vector<int> par(n + 1, -1);
    par[start] = start;
    queue<int> q;
    q.push(start);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        if(u == end) {
            break;
        }
        for(int v: adj2[u]) {
            if(par[v] == -1) {
                par[v] = u;
                q.push(v);
            }
        }
    }
    vector<int> path;
    for(int v = end; v != start; v = par[v]) {
        path.push_back(v);
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return path;
}

void solve() {
    // The problem is actually fairly easy - we want the exact same set of
    // *labeled* edges, and this has nothing to do with isomorphism. There is a
    // simple algorithm that trivially works. First find an edge that exists in
    // the first tree, but doesn't in the second. Then you create a cycle, and
    // we can easily show one of the edges in it doesn't exist in the second
    // tree. We remove that edge. It doesn't matter which tree we apply these
    // operations to, so we can simply do this on the first one. We keep both
    // an adjacency list and a matrix so that each cycle finding via BFS is
    // O(N), and because we have at most O(N) operations, inserting / erasing
    // from the adjacency list is quick and gives us an O(N^2) solution.

    vector<tuple<int, int, int, int, int>> ops;

    for(auto [a, b]: input_edges1) {
        if(has2[a][b]) {
            continue;
        }

        auto path = find_path(a, b);

        int ra = -1, rb = -1;
        for(int i = 0; i + 1 < (int)path.size(); i++) {
            if(!has1[path[i]][path[i + 1]]) {
                ra = path[i];
                rb = path[i + 1];
                break;
            }
        }

        has2[ra][rb] = has2[rb][ra] = false;
        adj2[ra].erase(find(adj2[ra].begin(), adj2[ra].end(), rb));
        adj2[rb].erase(find(adj2[rb].begin(), adj2[rb].end(), ra));
        has2[a][b] = has2[b][a] = true;
        adj2[a].push_back(b);
        adj2[b].push_back(a);

        ops.emplace_back(2, a, b, ra, rb);
    }

    cout << ops.size() << "\n";
    for(auto [p, a1, b1, a2, b2]: ops) {
        cout << p << " " << a1 << " " << b1 << " " << a2 << " " << b2 << "\n";
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
from collections import deque

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    n = int(next(it))

    # has1[u][v] = 1 if (u,v) is an edge in Berland (fixed)
    # has2[u][v] = 1 if (u,v) is an edge in Beerland (mutable)
    # Using bytearray rows keeps memory reasonable for n<=2000.
    has1 = [bytearray(n + 1) for _ in range(n + 1)]
    has2 = [bytearray(n + 1) for _ in range(n + 1)]

    edges1 = []

    # Read Berland edges
    for _ in range(n - 1):
        u = int(next(it)); v = int(next(it))
        has1[u][v] = 1
        has1[v][u] = 1
        edges1.append((u, v))

    # Read Beerland edges; build adjacency list
    adj2 = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = int(next(it)); v = int(next(it))
        has2[u][v] = 1
        has2[v][u] = 1
        adj2[u].append(v)
        adj2[v].append(u)

    def find_path(start: int, end: int) -> list[int]:
        """Return the unique path between start and end in the current Beerland tree."""
        par = [-1] * (n + 1)
        par[start] = start
        q = deque([start])

        while q:
            u = q.popleft()
            if u == end:
                break
            for v in adj2[u]:
                if par[v] == -1:
                    par[v] = u
                    q.append(v)

        # Reconstruct end -> start
        path = []
        v = end
        while v != start:
            path.append(v)
            v = par[v]
        path.append(start)
        path.reverse()
        return path

    ops = []  # list of (p, a1, b1, a2, b2)

    for a, b in edges1:
        # Already present in Beerland: skip
        if has2[a][b]:
            continue

        # Find Beerland path between a and b
        path = find_path(a, b)

        # Pick an edge on this path that is NOT in Berland => removable
        ra = rb = -1
        for i in range(len(path) - 1):
            x, y = path[i], path[i + 1]
            if not has1[x][y]:
                ra, rb = x, y
                break

        # Remove (ra, rb) from Beerland structures
        has2[ra][rb] = 0
        has2[rb][ra] = 0
        adj2[ra].remove(rb)  # linear in degree; total still OK for n<=2000
        adj2[rb].remove(ra)

        # Add (a, b) to Beerland structures
        has2[a][b] = 1
        has2[b][a] = 1
        adj2[a].append(b)
        adj2[b].append(a)

        # Record operation: always modify Beerland (p=2)
        ops.append((2, a, b, ra, rb))

    out = [str(len(ops))]
    out.extend(f"{p} {a1} {b1} {a2} {b2}" for (p, a1, b1, a2, b2) in ops)
    sys.stdout.write("\n".join(out))

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

These implementations follow the optimal constructive proof: perform exactly one edge-swap for each edge present in Berland but missing in Beerland, always removing a "wrong" edge from the created cycle.
