void dfs(int v, int p) {
    tin[v] = minAncestor[v] = ++timer;
    used[v] = 1;
    for(auto &e: g[v]) {
        int to, id;
        tie(to, id) = e;
        if(to == p) continue;
        if(used[to]) {
            minAncestor[v] = min(minAncestor[v], tin[to]);
        } else {
            dfs(to, v);
            minAncestor[v] = min(minAncestor[v], minAncestor[to]);
            if(minAncestor[to] > tin[v]) {
                isBridge[id] = true;
            }
        }
    }
}

void dfs1(int v, int p) {
    used[v] = 1;
    comp[v] = compid;
    for(auto &e: g[v]) {
        int to, id;
        tie(to, id) = e;
        
        if(isBridge[id]) { // avoid traversing from this edge. so we get full component.
            continue;
        }
        if(used[to]) {
            continue;
        }
        dfs1(to, v);
    }
}

for(int i = 1; i <= M; ++i) {
    if(isBridge[i]) {
         int u, v;
         tie(u, v) = edges[i];
         // connect two componets using edge.
         tree[comp[u]].push_back(comp[v]);
         tree[comp[v]].push_back(comp[u]);
    }
}

const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;

int N, M, timer, compid;

vector<pair<int, int>> g[MAXN];
bool used[MAXN], isBridge[MAXM];
int comp[MAXN], tin[MAXN], minAncestor[MAXN];

vector<int> tree[MAXN]; // Store 2-edge-connected component tree.(Bridge tree).

void dfs(int v, int p) {
    tin[v] = minAncestor[v] = ++timer;
    used[v] = 1;
    for(auto &e: g[v]) {
        int to, id;
        tie(to, id) = e;
        if(to == p) continue;
        if(used[to]) {
            minAncestor[v] = min(minAncestor[v], tin[to]);
        } else {
            dfs(to, v);
            minAncestor[v] = min(minAncestor[v], minAncestor[to]);
            if(minAncestor[to] > tin[v]) {
                isBridge[id] = true;
            }
        }
    }
}

void dfs1(int v, int p) {
    used[v] = 1;
    comp[v] = compid;
    for(auto &e: g[v]) {
        int to, id;
        tie(to, id) = e;
        
        if(isBridge[id]) { // avoid traversing from this edge. so we get full component.
            continue;
        }
        if(used[to]) {
            continue;
        }
        dfs1(to, v);
    }
}

vector<pair<int, int>> edges;

void addEdge(int from, int to, int id) {
    g[from].push_back({to, id});
    g[to].push_back({from, id});
    edges[id] = {from, to};
}

void initB() {

    for(int i = 0; i <= compid; ++i)
        tree[i].clear();
    for(int i = 1; i <= N; ++i)
        used[i] = false;
    for(int i = 1; i <= M; ++i)
        isBridge[i] = false;
    
    timer = 0;
    compid = 0;
}

void bridge_tree() {

    initB();
    
    dfs(1, -1); //Assuming graph is connected.
    
    for(int i = 1; i <= N; ++i)
        used[i] = 0;

    for(int i = 1; i <= N; ++i) {
        if(!used[i]) {
            dfs1(i, -1);
            ++compid;
        }
    }

    for(int i = 1; i <= M; ++i) {
        if(isBridge[i]) {
            int u, v;
            tie(u, v) = edges[i];
            // connect two componets using edge.
            tree[comp[u]].push_back(comp[v]);
            tree[comp[v]].push_back(comp[u]);
        }
    }
}

void init() {
    edges.clear(); edges.resize(M + 1);
    for(int i = 1; i <= N; ++i)
        g[i].clear();
}

void solve() {
    cin >> N >> M;

    init();

    for(int i = 1; i <= M; ++i) {
        int u, v;
        cin >> u >> v; addEdge(u, v, i);
    }

    bridge_tree();

}

You are standing on a grid, your current location is at point (X start, Y start) and you want to end up at point (X end, Y end).

In 1 second you can move in the 4 directions {UP, DOWN, LEFT, RIGHT}.

also given P distinct teleport portal points, you can go from any portal at position i to any other portal at position j in 0 second.

Now you want to calculate the minimum time needed to reach point the end point starting from the starting point.

You may assume that all positions/locations will be in range maxX * maxY ≤ 3 * 105 and (1 ≤ X) and (1 ≤ Y)

Input The first line will contain T (1 ≤ T ≤ 100) the number of test cases.

Each test case will begin with a line containing 2 positive integers P, Q, the number of teleport portal points and the number of queries respectively.

The next P lines will contain 2 integers (X i, Y i), the location of the i th portal.

The next Q lines will contain 4 integers (X start, Y start), (X end, Y end) the starting point and the ending point respectively.

Output For each test case, output Q lines containing the minimum time needed to reach the ending point of the i th query.

Scoring Subtask #1 (20 points): P = 0, Q = 1, Y i = Y start = Y end = 1 All points are on same line with y = 1

Subtask #2 (20 points): P = 2, Q = 1, Y i = Y start = Y end = 1 All points are on same line with y = 1

Subtask #3 (20 points): 2 ≤ P ≤ 105, Q = 1, Y i = Y start = Y end = 1 All points are on same line with y = 1

Subtask #4 (20 points): 2 ≤ P ≤ 105, Q ≤ 105, Y i = Y start = Y end = 1 All points are on same line with y = 1

Subtask #5 (10 points): 2 ≤ P ≤ 105, Q ≤ 105, Y i = Y j for any i and j, Every teleport is on same line with same y

Subtask #6 (10 points): 2 ≤ P ≤ 105, Q ≤ 105