## 1) Concise abridged problem statement

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

> For every two distinct vertices `u != v`, there is **exactly one** vertex that is adjacent to both `u` and `v` (exactly one common neighbor).

After the reform, roads start getting destroyed. Then 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 disconnected.

Constraints are not fully shown, but the number of queries is bounded; the solution must be fast.

---

## 2) Detailed editorial (solution explanation)

### Key structural theorem (Friendship theorem)

The condition

> every pair of distinct vertices has exactly one common neighbor

characterizes graphs known as **friendship graphs** (also called "windmill graphs"). A classic result (Erdős–Rényi–Sós, 1966) implies:

Such a graph must look like:

- There exists a single **central vertex** `c`
- All other vertices are partitioned into disjoint pairs `(a_i, b_i)`
- For each pair `(a_i, b_i)`, edges form a triangle `c - a_i - b_i - c`
- No other edges exist

So initially the graph is a bunch of triangles sharing the same center.

Consequences:

- The graph is connected initially (implied by the property).
- Every **non-center** vertex has degree exactly 2 initially: connected to `center` and to its **partner** in the triangle.
- The center has high degree: connected to all non-center vertices.

After deletions, this structure is partially broken, but edges are only removed, never added.

---

### What queries ask after deletions

We need shortest distances in the **current** graph.

Because the original graph is extremely restricted, even after deletions the remaining edges still come only from those triangles.

So the possible paths between two vertices are very limited:

- Any path between vertices in different triangles (different partner pairs) can only go through the center `c` (because there were no cross edges).
- Within the same triangle (center + two partners), there are only 3 edges to consider.

Thus for `LENGTH(x, y)` we can answer in O(1) if we can:
1. Identify the center `c`
2. For any vertex `v`, know its partner `partner[v]` (the other non-center vertex in its original triangle)
3. Quickly test whether a particular edge currently exists (because it may have been deleted)

---

### Finding the center

In the initial friendship graph:

- The center has degree `n-1` (connected to every other vertex)
- All non-center vertices have degree 2

So we can find `center` as the vertex with **maximum degree** in the initial graph.

Even if constraints were larger, this is linear in `n+m`.

---

### Finding each vertex's partner

For any `v != center`, its neighbors initially are `{center, partner[v]}`.

So we can set:

- `partner[v] =` the unique neighbor of `v` that is not `center` (or 0 if missing later, but we compute partners from the initial adjacency).

Important: deletions will remove edges, but the "intended partner" from the original structure stays the same and is still useful in reasoning about distances.

---

### Fast "does edge (u,v) exist currently?" with deletions

We must support deletions by index (`DELETE x` refers to the original `x`-th edge).

To delete in O(1), the C++ solution stores adjacency lists as `std::list<int>` and for each original edge `i` stores the **iterators** to the two list nodes representing it:

- When building adjacency: insert `v` into `adj[u]`, keep iterator
- Insert `u` into `adj[v]`, keep iterator
- On delete: erase both iterators in O(1)

To test existence of an edge `(u, v)` after deletions:

- Scan the smaller adjacency list between `adj[u]` and `adj[v]`
- Since at least one endpoint is non-center in all checks we perform, the smaller list is size ≤ 2 (or small), so this is O(1) in practice and in worst-case reasoning for this special graph.

---

### Distance logic

Define a helper `dist_to_center(v)`:

- `0` if `v == center`
- `1` if edge `(v, center)` exists
- `2` if edge `(v, partner[v])` exists AND edge `(partner[v], center)` exists
- otherwise `-1` (cannot reach center)

Then answer `LENGTH(x, y)`:

1. If `x == y`: `0`
2. If one is center: return `dist_to_center(other)`
3. If `partner[x] == y` (they are the two non-center vertices of the same triangle):
   - candidate distance 1 if edge `(x,y)` exists
   - candidate distance 2 if both `(x,center)` and `(center,y)` exist
   - take min, else `-1`
4. Otherwise (different triangles):
   - must go via center, if possible
   - compute `dx = dist_to_center(x)`, `dy = dist_to_center(y)`
   - if either is `-1` → `-1`, else `dx + dy`

This is correct because there are no edges between different triangles except via the center, and the only other possible intermediate is a vertex's partner.

Complexity:
- Building: O(n + m)
- Each `DELETE`: O(1)
- Each `LENGTH`: O(1) (small adjacency scans)
- Memory: O(n + m)

---

## 3) C++ Solution

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

---

## 4) Python solution (same approach) 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()
```

---

## 5) Compressed editorial

The "exactly one common neighbor for every pair" property implies (Friendship theorem) the initial graph is a **windmill**: all triangles share one **center** `c`; other vertices form disjoint partner pairs `(a,b)` with edges `c-a`, `c-b`, `a-b`. Pick `c` as the max-degree vertex.

Precompute `partner[v]` for each `v != c` as its neighbor different from `c`.

Maintain current graph under deletions and answer distances using only local checks:

- `dist(v,c)=0` if `v=c`, `1` if edge `(v,c)` exists, `2` if `(v,partner[v])` and `(partner[v],c)` exist, else `-1`.
- For query `(x,y)`:
  - if `x==y`: `0`
  - if one is `c`: `dist(other,c)`
  - if `partner[x]==y`: answer is `1` if `(x,y)` exists else `2` if both spokes to `c` exist else `-1`
  - otherwise: answer is `dist(x,c)+dist(y,c)` if both reachable, else `-1`.

C++ uses `std::list` adjacency plus stored iterators per edge for O(1) `DELETE`; edge existence is O(1) by scanning the smaller list (non-center degrees ≤2). Python can use adjacency `set`s with `discard`.
