#include <bits/stdc++.h>
using namespace std;
const int DIM = 1e5 + 5;
const int MOD = 1e9 + 7;
int n;
vector <int> v[5000];
int bfs(int nod) {
queue <int> q;
vector <bool> viz(n, 0);
vector <int> dist(n, 0);
q.push(nod);
viz[nod] = 1;
int ans = 0;
while (!q.empty()) {
int nod = q.front();
q.pop();
ans = ans + dist[nod];
for (auto it : v[nod]) {
if (!viz[it]) {
viz[it] = 1;
dist[it] = dist[nod] + 1;
q.push(it);
}
}
}
return ans;
}
int DistanceSum(int _n, int *X, int *Y) {
n = _n;
if (n <= 5000) {
for (int i = 0; i < n ; ++i) {
for (int j = i; j < n ; ++j) {
if ((X[i] == X[j] && abs(Y[i] - Y[j]) == 1) || (Y[i] == Y[j] && abs(X[i] - X[j]) == 1)) {
v[i].push_back(j);
v[j].push_back(i);
}
}
}
long long sol = 0;
for (int i = 0; i < n ; ++i) sol += bfs(i);
sol = sol / 2;
sol %= MOD;
return sol;
}
return n;
}
/**
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
**/
