Problem 1. Tree Boxes

USACO 2019 US Open Contest, Platinum

Farmer John计划建造$N$（$1 \leq N \leq 10^5$）个农场，由$N-1$条道路连通，构成一棵树。通常，当他的一个农场出现问题时，他不会被告知具体出现了问题的农场。取而代之的是，他会被告知从某个农场$A$到某个农场$B$的路径上的农场之一出现了问题。这经常使Farmer John感到困惑，因为他平时都驾驶越野拖拉机，所以对道路系统并不熟悉。

Farmer John将农场的位置视为二维坐标系中的点。他更希望被告知出现问题的是某个四边平行于坐标轴的长方形区域中的某个农场。这样Farmer John就可以自己决定如何在农场之间通行。Bessie告诉他这有些太困难了，所以只要他被告知两个不包含相同农场并且总共包含了沿$A$到$B$路径上的所有农场的四边与坐标轴平行的长方形，他就满意了。你需要帮助Farmer John决定他应当建造他的农场的位置，使得这一条件被满足。

这是一道交互题，你不可以使用标准（或文件）输入输出。

使用标准（或文件）输入输出的程序将会被取消成绩。

然而，你

可以

使用全局或是静态变量。为了帮助Farmer John，你需要实现如下函数：

• void addRoad(int A, int B)：处理一条建造在农场$A$和$B$之间的道路（$0 \le A, B \le N - 1$）。
• void buildFarms()：确定Farmer John需要建造所有农场的位置。
• void notifyFJ(int A, int B)：告知Farmer John满足前述条件的一个或两个长方形。

你对上述函数的实现中可以调用下面给出的函数。假设$\texttt{notifyFJ}$会被调用$Q$次（$1 \le Q \leq 10^5$）。

• int getN()：获得$N$的值。
• int getQ()：获得$Q$的值。
• void setFarmLocation(int ID, int X, int Y)：决定Farmer John应当将农场$ID$（$0 \le ID \le N-1$）建造在位置$(X,Y)$，其中$1 \le X, Y \le N$。应当仅被$\texttt{buildFarms}$调用。
• void addBox(int X1, int Y1, int X2, int Y2)：增加一个告知Farmer John的长方形，其中$1 \le X1 \le X2 \le N$， $1 \le Y1 \le Y2 \le N$。应当仅被$\texttt{notifyFJ}$调用。

交互方式如下。首先，$\texttt{addRoad}$会被调用$N-1$次，用来告知你的程序道路系统。接下来，$\texttt{buildFarms}$会被调用，你需要确定Farmer John需要建造每个农场的位置，并且相应地为每个农场调用$\texttt{setFarmLocation}$。最后，会有$Q$次对$\texttt{notifyFJ}$的调用，在每次调用中你必须调用一次或两次$\texttt{addBox}$来告知Farmer John。

保证始终存在一种符合条件的方式可以使用一个或两个长方形来告知Farmer John。这个问题的运行内存限制为512MB，超过一般问题所给的256MB内存限制。

C++的程序请使用下面的模板：

#include "grader.h"

void addRoad(int a, int b){
    // Fill in code here
}

void buildFarms(){
    // Fill in code here
}

void notifyFJ(int a, int b){
    // Fill in code here
}

Java的程序请使用下面的模板：

import java.io.IOException;
// If you find it necessary, you may import other standard libraries here.
public class boxes extends Grader {

    // Copy this exactly:
        
Override
    public static void main(String args[]) throws IOException { new boxes().run(); }

        
Override
    public void addRoad(int a, int b) {
      // Fill in code here
    }
        
Override
    public void buildFarms(){
      // Fill in code here
    }
    
Override
    public void notifyFJ(int a, int b){
      // Fill in code here
    }
}

交互样例： 评测机调用$\texttt{addRoad(0,1)}$

评测机调用$\texttt{addRoad(1,2)}$

评测机调用$\texttt{buildFarms()}$

选手程序调用$\texttt{setFarmLocation(0,1,1)}$

选手程序调用$\texttt{setFarmLocation(1,1,2)}$

选手程序调用$\texttt{setFarmLocation(2,2,2)}$

选手程序结束$\texttt{buildFarms()}$

评测机调用$\texttt{notifyFJ(0,0)}$

选手程序调用$\texttt{addBox(1,1,1,1)}$

选手程序结束$\texttt{notifyFJ(0,0)}$

评测机调用$\texttt{notifyFJ(0,2)}$

选手程序调用$\texttt{addBox(1,1,1,2)}$

选手程序调用$\texttt{addBox(2,2,2,2)}$

选手程序结束$\texttt{notifyFJ(0,2)}$

评测结束，选手程序通过测试用例

供题：Spencer Compton