#include "grader.h"

// int getN(): gets the value of N.
// int getQ(): gets the value of Q.
// void setFarmLocation(int ID, int X, int Y): determines that Farmer John should build farm ID (0≤ID≤N−1) at location (X,Y) where (1≤X,Y≤N). Should only be called from buildFarms.
// void addBox(int X1, int Y1, int X2, int Y2): adds a box to notify Farmer John where (1≤X1≤X2≤N) and (1≤Y1≤Y2≤N). Should only be called from notifyFJ.

// MEMORY LIMIT: 512 MB
// (increased from usual 256 MB)
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5;
const int LOG = 20;

int n, q;

vector<int> adj[maxn];
int bl[maxn][LOG];
int dpth[maxn];
int subsz[maxn];
pair<int,int> coords[maxn];

void add_edge(int a, int b) {
    adj[a].push_back(b);
    adj[b].push_back(a);
}

int getsubsz(int nd, int par) {
    subsz[nd] = 1;
    for (auto i : adj[nd])
        if (i != par)
            subsz[nd] += getsubsz(i, nd);
    return subsz[nd];
}

void init(int nd, int d) {
    dpth[nd] = d;
    for (int i = 1; i < LOG; i++)
        bl[nd][i] = bl[bl[nd][i - 1]][i - 1];
    for (auto i : adj[nd])
        if (i != bl[nd][0]) {
            bl[i][0] = nd;
            init(i, d + 1);
        }
}

int jmp(int nd, int k) {
    for (int i = 0; i < LOG; i++)
        if (1 & (k >> i))
            nd = bl[nd][i];
    return nd;
}
int lca(int a, int b) {
    if (dpth[a] > dpth[b])
        swap(a, b); // dpth[b] > dpth[a] now
    b = jmp(b, dpth[b] - dpth[a]);
    if (a == b)
        return a;
    for (int i = LOG - 1; i >= 0; i--) {
        int A = bl[a][i], B = bl[b][i];
        if (A != B)
            a = A, b = B;
    }
    return bl[a][0];
}


int edges_added = 0;
void addRoad(int a, int b) {
    n = getN();
    q = getQ();

    add_edge(a, b);
    edges_added++;

    if (edges_added == n - 1)
        init(0, 0);
}

int place(int nd, int a, int b) {
    setFarmLocation(nd, a, b);
    coords[nd] = {a, b};
    a += subsz[nd], b++;
    for (auto i : adj[nd])
        if (i != bl[nd][0]) {
            a -= subsz[i];
            b = place(i, a, b);
        }
    return b;
}

void buildFarms() {
    getsubsz(0, -1);
    place(0, 1, 1);
}

pair<pair<int,int>, pair<int,int>> getBOX(int a, int b) {
    return {coords[a], coords[b]};
}

void callBox(int a, int b) {
    auto x = getBOX(a, b);
    addBox(x.first.first, x.first.second, x.second.first, x.second.second);
}

void notifyFJ(int a, int b) {
    int c = lca(a, b);
    if (c == a) swap(a, b);
    if (c == b) {
        callBox(c, a);
    } else {
        callBox(c, a);
        callBox(jmp(b, dpth[b] - dpth[c] - 1), b);
    }
}