<|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.

384. Country
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Once upon a time in a faraway kingdom there was a very wise King. This King wanted to improve the road system of the country. For the purposes of this problem the road system can be considered as an undirected graph without loops and parallel edges (the vertices of this graph correspond to the cities and the edges correspond to the roads). The King was fond of mathematics, so he reformed the road system of the kingdom in the following mathematical way: for each two distinct cities there was exactly one common neighbour (any city is not neighbour of itself). The road reform was successful, but with the lapse of time some roads were destroyed. The government of the kingdom wants to know the distances between cities at any moment of time. Your task is to help the government with this problem.

Input
The first line of the input contains two integer numbers n and m — the number of cities and the number of roads immediately after the reform (). The next m lines describe the roads of the kingdom. Each of these lines contains two integer numbers xi and yi — 1-based indices of cities connected by this road. The following lines describe queries of the government and information about road destruction. If the line describes a destruction of the road, it will be formatted as "DELETE x", where x is 1-based index of the road. Otherwise it will be formated as "LENGTH x y", where x and y are 1-based indices of cities. The queries will appear in the input till the end of the file. The total number of queries doesn't exceed .

Output
For each "LENGTH" query output the answer on the separate line, or -1 if there's no way to travel from one city to another.

Example(s)
sample input
sample output
3 3
1 2
2 3
3 1
LENGTH 1 2
DELETE 1
LENGTH 1 2
LENGTH 2 3
DELETE 3
LENGTH 1 2
1
2
1
-1

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

You are given an undirected simple graph with `n` cities and `m` roads **as it was right after a “reform”**. The reformed graph satisfied:

> For every two distinct vertices `u != v`, there is **exactly one** common neighbor.

After that, roads get destroyed over time. You must process operations until EOF:

- `DELETE x` — delete the `x`-th road from the original list (1-based).
- `LENGTH x y` — output the current shortest path length between cities `x` and `y`, or `-1` if they are disconnected.

Constraints are such that you need a very fast per-query solution.

---

## 2) Key observations

### Observation A: The initial graph is a “friendship/windmill graph”
A classic theorem (Friendship theorem) states that a finite simple graph where **every pair of vertices has exactly one common neighbor** must have a very specific shape:

- There exists a unique **center** vertex `c`.
- All other vertices are partitioned into disjoint pairs `(a_i, b_i)`.
- For each pair, edges form a triangle: `c-a_i`, `c-b_i`, `a_i-b_i`.
- There are **no edges** between vertices belonging to different pairs (except through the center).

So the graph is a set of triangles all sharing one common vertex.

### Observation B: Degrees in the reformed graph
- The center `c` has degree `n-1`.
- Every non-center vertex has degree exactly `2` (connected to `c` and to its triangle partner).

So the center can be found as the vertex with maximum degree in the initial graph.

### Observation C: Even after deletions, structure stays local
Edges are only deleted, never added, so the remaining graph is a subgraph of those triangles. Therefore, any shortest path can only be:

- inside one triangle, or
- between triangles via the center (if possible).

Hence distances can be answered using a few constant-time edge existence checks.

---

## 3) Full solution approach

### Step 1: Read the initial graph and store edges
Store the original edge list `edges[i] = (u, v)` so that `DELETE x` can refer to it.

### Step 2: Identify the center
Build initial adjacency and select the vertex with maximum degree as `center`.

### Step 3: Precompute each non-center vertex’s partner
For each vertex `v != center`, in the original graph it had exactly two neighbors:
- `center`
- `partner[v]` (the other vertex in its triangle)

So `partner[v]` is “the neighbor of `v` that is not `center`” (from the initial adjacency).

### Step 4: Maintain current edges under deletions
You need:
- delete an edge fast
- test whether an edge exists fast

Two common implementations:

**C++ (worst-case O(1) delete):**
- Store adjacency as `std::list<int>` for each vertex.
- When inserting an edge `(u, v)`, store iterators to the list nodes in both adjacency lists.
- On `DELETE`, erase those iterators in O(1).

**Python (simple, fast enough here):**
- Store adjacency as `set` per vertex.
- On `DELETE`, do `discard()` from both sets (average O(1)).
- Edge existence is `v in adj[u]` (average O(1)).

### Step 5: Answering distances

Define:

`has_edge(u, v)` — whether the edge currently exists.

Define distance from `v` to the center:

```
dist_to_center(v):
  if v == center: return 0
  if edge(v, center) exists: return 1
  let p = partner[v]
  if edge(v, p) exists AND edge(p, center) exists: return 2
  else return -1
```

Now answer `LENGTH(x, y)`:

1. If `x == y` → `0`.
2. If one is `center` → `dist_to_center(other)`.
3. If `partner[x] == y` (same original triangle):
   - distance `1` if edge `(x, y)` exists
   - distance `2` if both `(x, center)` and `(center, y)` exist
   - otherwise `-1`
4. Otherwise they are from different triangles:
   - any path must go through `center`
   - answer is `dist_to_center(x) + dist_to_center(y)` if both not `-1`, else `-1`.

**Why this is correct:**  
There are no cross edges between triangles in the original graph; deletions cannot create new ones. So any inter-triangle route must go through the center. Inside a triangle, only the 3 edges matter.

---

## 4) C++ implementation (with detailed comments)

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

/*
  Country (p384) solution.

  Key idea: By the Friendship theorem, the initial graph is a "windmill":
  many triangles sharing one common center vertex c.

  After deletions, edges are removed but never added, so the graph remains
  a subgraph of those triangles. Distances can be answered by checking only
  a few edges around the center and triangle partners.

  We maintain adjacency as std::list<int> to support O(1) deletion by iterator.
*/

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

    int n, m;
    cin >> n >> m;

    vector<pair<int,int>> edges(m);
    for (int i = 0; i < m; i++) cin >> edges[i].first >> edges[i].second;

    // Adjacency as linked list; allows O(1) erase if we store iterators.
    vector<list<int>> adj(n + 1);

    // For each original edge i, store iterators to the adjacency list nodes:
    // iters[i][0] is the node in adj[u] that stores v
    // iters[i][1] is the node in adj[v] that stores u
    vector<array<list<int>::iterator, 2>> iters(m);

    // Build adjacency and store iterators for each edge.
    for (int i = 0; i < m; i++) {
        auto [u, v] = edges[i];

        iters[i][0] = adj[u].insert(adj[u].end(), v);
        iters[i][1] = adj[v].insert(adj[v].end(), u);
    }

    // Find the center: vertex with maximum degree in the initial graph.
    int center = 1;
    for (int v = 2; v <= n; v++) {
        if (adj[v].size() > adj[center].size()) center = v;
    }

    // partner[v] for v != center: the unique neighbor of v that isn't center.
    vector<int> partner(n + 1, 0);
    for (int v = 1; v <= n; v++) {
        if (v == center) continue;
        for (int u : adj[v]) {
            if (u != center) {
                partner[v] = u;
                break;
            }
        }
    }

    // Check if an edge (u, v) currently exists.
    // We scan the smaller adjacency list.
    // In this problem's structure, at least one endpoint is usually non-center,
    // hence degree <= 2, so this is effectively O(1).
    auto has_edge = [&](int u, int v) -> bool {
        if (adj[u].size() > adj[v].size()) swap(u, v);
        for (int w : adj[u]) if (w == v) return true;
        return false;
    };

    // Current shortest distance from v to center: {0,1,2} or -1 if unreachable.
    function<int(int)> dist_to_center = [&](int v) -> int {
        if (v == center) return 0;
        if (has_edge(v, center)) return 1;

        int p = partner[v];
        if (p != 0 && has_edge(v, p) && has_edge(p, center)) return 2;

        return -1;
    };

    // Answer a LENGTH query for current graph.
    auto query_length = [&](int x, int y) -> int {
        if (x == y) return 0;

        if (x == center || y == center) {
            int other = (x == center ? y : x);
            return dist_to_center(other);
        }

        // Same original triangle?
        if (partner[x] == y) {
            int best = INT_MAX;

            if (has_edge(x, y)) best = min(best, 1);
            if (has_edge(x, center) && has_edge(center, y)) best = min(best, 2);

            return (best == INT_MAX ? -1 : best);
        }

        // Different triangles -> must go via center
        int dx = dist_to_center(x);
        int dy = dist_to_center(y);
        if (dx == -1 || dy == -1) return -1;
        return dx + dy;
    };

    // Process commands until EOF.
    string cmd;
    while (cin >> cmd) {
        if (cmd == "DELETE") {
            int x;
            cin >> x;
            --x; // to 0-based edge index

            auto [u, v] = edges[x];

            // Erase the two adjacency nodes in O(1) using stored iterators.
            adj[u].erase(iters[x][0]);
            adj[v].erase(iters[x][1]);
        } else if (cmd == "LENGTH") {
            int x, y;
            cin >> x >> y;
            cout << query_length(x, y) << "\n";
        }
    }

    return 0;
}
```

---

## 5) Python implementation (with detailed comments)

```python
import sys

"""
Python version.

We use adjacency as sets:
- DELETE: discard from both sets (average O(1))
- has_edge: membership test (average O(1))

This is typically fast enough given the special structure (windmill triangles).
"""

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

    n = int(next(it))
    m = int(next(it))

    edges = []
    adj = [set() for _ in range(n + 1)]

    # Read initial edges and build adjacency sets.
    for _ in range(m):
        u = int(next(it)); v = int(next(it))
        edges.append((u, v))
        adj[u].add(v)
        adj[v].add(u)

    # Find center (max degree in the initial graph).
    center = 1
    for v in range(2, n + 1):
        if len(adj[v]) > len(adj[center]):
            center = v

    # partner[v] for v != center: the non-center neighbor in the initial triangle.
    partner = [0] * (n + 1)
    for v in range(1, n + 1):
        if v == center:
            continue
        for u in adj[v]:
            if u != center:
                partner[v] = u
                break

    def has_edge(u: int, v: int) -> bool:
        return v in adj[u]

    def dist_to_center(v: int) -> int:
        if v == center:
            return 0
        if has_edge(v, center):
            return 1
        p = partner[v]
        if p != 0 and has_edge(v, p) and has_edge(p, center):
            return 2
        return -1

    def query_length(x: int, y: int) -> int:
        if x == y:
            return 0

        if x == center or y == center:
            other = y if x == center else x
            return dist_to_center(other)

        # Same original triangle?
        if partner[x] == y:
            best = None
            if has_edge(x, y):
                best = 1
            if has_edge(x, center) and has_edge(center, y):
                best = 2 if best is None else min(best, 2)
            return -1 if best is None else best

        # Different triangles -> must go via center
        dx = dist_to_center(x)
        dy = dist_to_center(y)
        if dx == -1 or dy == -1:
            return -1
        return dx + dy

    out = []

    # Remaining tokens are commands until EOF.
    # Commands are ASCII words: DELETE / LENGTH
    for token in it:
        cmd = token.decode()
        if cmd == "DELETE":
            idx = int(next(it)) - 1
            u, v = edges[idx]
            adj[u].discard(v)
            adj[v].discard(u)
        else:  # LENGTH
            x = int(next(it))
            y = int(next(it))
            out.append(str(query_length(x, y)))

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

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

This completes a structured, efficient solution based on the friendship (windmill) structure, supporting deletions and shortest-path queries quickly.