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

174. Walls
time limit per test: 0.75 sec.
memory limit per test: 32768 KB
input: standard
output: standard



People of country T-land lived on the big plain many years ago. It is happened so that they started to quarrel, so they began to build walls to separate from each other.
One day they realized that walls surround some part of the country. Your task is to determine which wall was build first to surround a part of the T-land.

Input
The first line of input contains one number M (1<=M<=200000) - number of walls. Each of the following M lines contains four integer numbers: Cartesian coordinates of two ends of each wall. Walls are rectilinear segments with positive length, two walls can cross only by ends, and walls can't coincide. All coordinates do not exceed 10^9 by its absolute values.

Output
Write the answer in the single line of output. If all the walls leave the territory opened, write 0.

Sample test(s)

Input
4
0 0 1 0
0 1 0 0
1 0 0 1
2 2 5 7

Output
3
Author:	Dmitry Orlov
Resource:	Saratov ST team Spring Contest #1
Date:	18.05.2003

<|response|>
1. Abridged problem statement  
We are given M axis-aligned wall segments in the plane. Walls only meet or cross at their endpoints, and no two walls coincide. Walls are added one by one in a given order. We must find the 1-based index of the first wall whose addition closes a cycle of walls (i.e., whose two endpoints were already connected by earlier walls). If no wall ever completes a cycle, output 0.

2. Key observations  
- Model the endpoints as graph vertices and walls as edges in an undirected graph.  
- Adding an edge that connects two vertices already in the same connected component creates a cycle.  
- Disjoint-Set Union (DSU) can maintain connectivity and detect when two vertices are already connected in nearly O(1) amortized time.  
- Each unique endpoint coordinate pair can be mapped to a distinct integer ID using a hash map (or std::map).

3. Full solution approach  
1. Initialize a DSU structure sized for up to 2·M elements, since there are at most 2 endpoints per wall.  
2. Initialize an empty map from point (x,y) to integer ID, and a counter nextID = 0.  
3. For each wall i from 1 to M:  
   a. Read endpoints (x1,y1) and (x2,y2).  
   b. If (x1,y1) is not in the map, assign it map[(x1,y1)] = nextID++. Likewise for (x2,y2).  
   c. Let u = map[(x1,y1)], v = map[(x2,y2)].  
   d. If find(u) == find(v) in the DSU, then adding this edge would form a cycle. Print i and terminate.  
   e. Otherwise, unite(u, v) in the DSU.  
4. If no cycle is found after processing all walls, print 0.

Time complexity: O(M α(M)) for DSU operations plus O(M) expected for map lookups.  
Memory usage: O(M) for DSU and map.

4. C++ implementation
```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/dsu.hpp>

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

class DSU {
  public:
    int n;
    vector<int> par;
    vector<int> sz;

    DSU(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 0);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
    bool connected(int x, int y) { return root(x) == root(y); }

    int unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) {
            return x;
        }
        if(sz[x] > sz[y]) {
            swap(x, y);
        }
        par[x] = y;
        sz[y] += sz[x];
        return y;
    }
};

int m;

void read() { cin >> m; }

void solve() {
    // The walls form a planar graph whose vertices are the endpoints; a region
    // becomes enclosed exactly when adding a wall creates the first cycle.
    // Maintain a DSU over endpoints (each distinct coordinate pair gets an id
    // via get_id). For each wall, if its two endpoints are already in the same
    // component the wall closes a cycle, so print its 1-based index; otherwise
    // union the components. If no wall ever closes a cycle, print 0.

    DSU dsu(2 * m);
    map<pair<int, int>, int> mp;

    function<int(int, int)> get_id = [&](int x, int y) {
        if(mp.count({x, y})) {
            return mp[{x, y}];
        }
        return mp[{x, y}] = mp.size();
    };

    for(int i = 0; i < m; i++) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        if(dsu.connected(get_id(x, y), get_id(a, b))) {
            cout << i + 1 << '\n';
            return;
        }

        dsu.unite(get_id(x, y), get_id(a, b));
    }

    cout << 0 << '\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments
```python
import sys
sys.setrecursionlimit(10**7)

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, a, b):
        ra = self.find(a)
        rb = self.find(b)
        if ra == rb:
            return False    # already in same set → would form a cycle
        if self.size[ra] > self.size[rb]:
            ra, rb = rb, ra
        self.parent[ra] = rb
        self.size[rb] += self.size[ra]
        return True

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    M = int(next(it))

    dsu = DSU(2 * M)     # at most 2*M unique endpoints
    point_id = {}        # map (x,y) → unique integer ID
    next_id = 0

    for i in range(1, M + 1):
        x1 = int(next(it)); y1 = int(next(it))
        x2 = int(next(it)); y2 = int(next(it))

        # assign/get ID for first endpoint
        if (x1, y1) not in point_id:
            point_id[(x1, y1)] = next_id
            next_id += 1
        u = point_id[(x1, y1)]

        # assign/get ID for second endpoint
        if (x2, y2) not in point_id:
            point_id[(x2, y2)] = next_id
            next_id += 1
        v = point_id[(x2, y2)]

        # if unite returns False, a cycle is formed here
        if not dsu.unite(u, v):
            print(i)
            return

    # no cycle formed after all walls
    print(0)

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