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

```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, m;
vector<pair<int, int>> edges;

void read() {
    cin >> n >> m;
    edges.resize(m);
    cin >> edges;
}

int center;
vector<int> partner;
vector<list<int>> adj;
vector<array<list<int>::iterator, 2>> edge_iters;

bool has_edge(int u, int v) {
    if(adj[u].size() > adj[v].size()) {
        swap(u, v);
    }
    for(int w: adj[u]) {
        if(w == v) {
            return true;
        }
    }
    return false;
}

int dist_to_center(int v) {
    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;
}

int query_length(int x, int y) {
    if(x == y) {
        return 0;
    }
    if(x == center || y == center) {
        int other = (x == center) ? y : x;
        return dist_to_center(other);
    }
    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;
    }
    int dx = dist_to_center(x);
    int dy = dist_to_center(y);
    if(dx == -1 || dy == -1) {
        return -1;
    }
    return dx + dy;
}

void solve() {
    // The key observation is that "for each two distinct cities there was
    // exactly one common neighbour" is closely related to the Friendship
    // Theorem (Erdos - Renyi - Sos, 1966). In particular, each possible input
    // graph can be constructed as follows:
    //
    //     1) Take some central vertex c.
    //
    //     2) Add k >= 1 pairwise disjoint edges (a matching) on 2k additional
    //        vertices.
    //
    //     3) Connect each of the 2k vertices in (2) to c.
    //
    // In other words, the possible graphs can be constructed as triangles that
    // share one vertex (the central vertex c). Note that the statement implies
    // that the graph is connected, meaning we can always find some vertex c. It
    // also implies that m = O(n), so we can read the input (note the problem
    // statement doesn't give the constraint for m, which is a hint).
    //
    // In terms of queries, we can do a few things. Arguably the simplest
    // approach is to start with finding c (we can choose the highest degree
    // vertex) and then decomposing the input into triangles (c will be shared
    // across all). Now when we have a query, we have two cases:
    //
    //     1) u and v are in the same triangle. Then we can check the 3 edges in
    //       the corresponding triangle and figure out if the answer is 1, 2, or
    //       no path.
    //
    //     2) u and v are in different triangles. Then the path certainly passes
    //        through the center c. We can output query(u, c) + query(c, v).
    //
    // Implementing this with sets for the graph and pairs of vertices that
    // belong to the same triangle is already enough to pass in O((n + q) log
    // n). Here we go one step further and implement the linear O(n + q)
    // version:
    //
    //     - Every non-center vertex has degree at most 2 (its two triangle
    //       neighbours: c and its partner). So has_edge(u, v) can be resolved
    //       by always scanning the smaller adjacency list, giving
    //       O(min(|adj[u]|, |adj[v]|)) = O(1) since at least one endpoint is
    //       non-center.
    //
    //     - For deletions we only need O(1) edge removal. We store each edge in
    //       a std::list adjacency on both endpoints and remember the two
    //       iterators at insertion time; on DELETE we just erase by iterator.

    adj.assign(n + 1, list<int>());
    edge_iters.resize(m);
    for(int i = 0; i < m; i++) {
        auto [u, v] = edges[i];
        edge_iters[i][0] = adj[u].insert(adj[u].end(), v);
        edge_iters[i][1] = adj[v].insert(adj[v].end(), u);
    }

    center = 1;
    for(int v = 2; v <= n; v++) {
        if(adj[v].size() > adj[center].size()) {
            center = v;
        }
    }

    partner.assign(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;
            }
        }
    }

    string cmd;
    while(cin >> cmd) {
        if(cmd == "DELETE") {
            int x;
            cin >> x;
            x--;
            auto [u, v] = edges[x];
            adj[u].erase(edge_iters[x][0]);
            adj[v].erase(edge_iters[x][1]);
        } else if(cmd == "LENGTH") {
            int x, y;
            cin >> x >> y;
            cout << query_length(x, y) << "\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 (with detailed comments)

```python
import sys

# We will implement the same logic.
# Python does not have stable list iterators like C++ std::list, so O(1) deletion
# by stored iterator is not convenient.
#
# However, in a friendship graph:
# - Every non-center vertex starts with degree 2 (center + partner)
# - Only deletions happen, so degree only decreases.
#
# Therefore we can store adjacency as small sets and delete in O(1) average time.
# Checking edge existence is also O(1) average.
#
# Complexity: O(n + m + q) average, which is fine for this structure.

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, 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 as vertex with maximum 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] = the non-center neighbor of v in its original triangle
    partner = [0] * (n + 1)
    for v in range(1, n + 1):
        if v == center:
            continue
        # Among neighbors, the one that is not the center is the partner
        for u in adj[v]:
            if u != center:
                partner[v] = u
                break

    def has_edge(u: int, v: int) -> bool:
        # With sets, membership is O(1) average.
        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 (partners)
        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 through center
        dx = dist_to_center(x)
        dy = dist_to_center(y)
        if dx == -1 or dy == -1:
            return -1
        return dx + dy

    out_lines = []

    # Remaining tokens describe commands until EOF.
    for token in it:
        cmd = token.decode()
        if cmd == "DELETE":
            x = int(next(it)) - 1  # to 0-based
            u, v = edges[x]
            # Remove if present (they always should be, but safe anyway)
            adj[u].discard(v)
            adj[v].discard(u)
        else:  # "LENGTH"
            x = int(next(it))
            y = int(next(it))
            out_lines.append(str(query_length(x, y)))

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

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

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