func_code_string: #include <bits/stdc++.h>   using namespace std;   const int INF = (1 << 30) - 1;   const long long mod = 1e9 + 9;   map<pair<int, int>, int> mp;   int m;   int v[100010][2];   int vis[100010];   int ans[100010], anscnt;   int up[100010][3];   int down[100010][3];   priority_queue<int> qmax;   priority_queue<int, vector<int>, greater<int> > qmin;   bool check(int a) {     for (int i = 0; i < 3; ++i)       if (up[a][i]) {         int id = up[a][i], cnt = 0;         for (int j = 0; j < 3; ++j) cnt += !down[id][j];         if (cnt == 2) return false;       }     return true;   }   bool Check(int a, int x) {     for (int i = 0; i < 3; ++i)       if (up[a][i]) {         int id = up[a][i], cnt = 0;         if (id == x) continue;         for (int j = 0; j < 3; ++j) cnt += !down[id][j];         if (cnt == 2) return false;       }     return true;   }   void Remove(int a) {     int now;     for (int i = 0; i < 3; ++i)       if (up[a][i]) {         int id = up[a][i];         for (int j = 2; j >= 0; --j)           if (down[id][j]) {             now = down[id][j];             if (now == a) down[id][j] = 0;           }       }     for (int i = 0; i < 3; ++i)       if (down[a][i]) {         int id = down[a][i];         for (int j = 2; j >= 0; --j)           if (up[id][j]) {             now = up[id][j];             if (now == a) up[id][j] = 0;           }       }   }   void Topo() {     anscnt = 0;     for (int i = 1; i <= m; ++i)       if (check(i)) {         qmax.push(i);         qmin.push(i);       }     int cur = 1;     while (1) {       int x;       if (cur % 2) {         if (qmax.empty()) break;         x = qmax.top();         qmax.pop();         if (vis[x]) continue;       } else {         if (qmin.empty()) break;         x = qmin.top();         qmin.pop();         if (vis[x]) continue;       }       if (check(x) == false) continue;       cur++;       vis[x] = 1;       ans[++anscnt] = x;       for (int i = 0; i < 3; ++i)         if (down[x][i]) {           int id = down[x][i];           if (Check(id, x)) {             qmax.push(id);             qmin.push(id);           }         }       Remove(x);     }   }   int main() {     scanf( %d , &m);     for (int i = 1; i <= (m); ++i) {       scanf( %d%d , &v[i][0], &v[i][1]);       mp[make_pair(v[i][0], v[i][1])] = i;     }     for (int i = 1; i <= (m); ++i) {       int id, a = v[i][0], b = v[i][1];       if (mp.find(make_pair(a - 1, b - 1)) != mp.end())         down[i][0] = mp[make_pair(a - 1, b - 1)];       if (mp.find(make_pair(a, b - 1)) != mp.end())         down[i][1] = mp[make_pair(a, b - 1)];       if (mp.find(make_pair(a + 1, b - 1)) != mp.end())         down[i][2] = mp[make_pair(a + 1, b - 1)];       if (mp.find(make_pair(a - 1, b + 1)) != mp.end())         up[i][0] = mp[make_pair(a - 1, b + 1)];       if (mp.find(make_pair(a, b + 1)) != mp.end())         up[i][1] = mp[make_pair(a, b + 1)];       if (mp.find(make_pair(a + 1, b + 1)) != mp.end())         up[i][2] = mp[make_pair(a + 1, b + 1)];     }     Topo();     long long rlt = 0;     for (int i = 1; i <= anscnt; ++i) rlt = (rlt * m % mod + ans[i] - 1) % mod;     printf( %I64d n , rlt);     return 0;   }   