406810: GYM102562 K Dense Settlements

In a long forgotten realm, there are $$$1 \leq N \leq 2 \times 10^5$$$ houses positioned in a 2D plane. House number $$$i$$$ has coordinates $$$(x_i, y_i)$$$, where $$$0 \leq x_i \leq 2 \times 10^9$$$ and $$$0 \leq y_i \leq 2 \times 10^9$$$. In this kingdom, houses are generally not too close to each other. We know that for every house, there exist at most $$$T \leq 20$$$ houses within distance $$$R \leq 2 \times 10^9$$$ from it, where the distance function is the squared Euclidean distance. Formally, the squared Euclidean distance is defined as $$$dist((x_i, y_i), (x_j, y_j)) = (x_i - x_j)^2 + (y_i - y_j)^2$$$. Below, it is understood that a neighbour of a house is another house within squared Euclidean distance R from it.

Since being around neighbours is important for safety purposes, we call a house "safe" if it has at least $$$K \leq 10$$$ neighbours. Travelling from a safe house to another neighbouring safe house is safe and encounters a danger level of 0. Besides travelling between reachable safe houses, there also exist $$$1 \leq M \leq 5 \times 10^5$$$ forest roads, each joining a pair of houses $$$(i, j)$$$ with a total danger corresponding to the squared Euclidean distance between houses $$$i$$$ and $$$j$$$. It is guaranteed that getting between any pair of houses is possible. Note that it is only possible to travel between neighbouring safe houses or using the forest road system.

The king of this magical kingdom occasionally reviews the danger of traveling throughout his empire. The danger of a path between houses $$$i$$$ and $$$j$$$ is defined as the maximum danger encountered on any given road part of this path. The king has just asked his advisors to figure out for $$$1 \leq Q \leq 2 \times 10^5$$$ pairs of cities what is the minimum danger a citizen will encounter, should they choose an optimal path.

Knowing they will not be able to tackle such a phenomenal task, the king's advisors enlist your help!

The first line of the input will contain $$$6$$$ numbers: $$$N$$$, $$$R$$$, $$$K$$$, $$$T$$$, $$$M$$$, $$$Q$$$ as defined above.

The following $$$N$$$ line will contain $$$2$$$ numbers each: $$$x_i$$$ and $$$y_i$$$, the coordinates of house $$$i$$$.

The next $$$M$$$ lines each contain $$$2$$$ numbers $$$i$$$, $$$j$$$ meaning there is a 2 way forest road edge between $$$i$$$ and $$$j$$$.

The following $$$Q$$$ lines each contain a pair of numbers $$$i$$$ and $$$j$$$ meaning that you are asked to compute the minimal danger of getting from house $$$i$$$ to house $$$j$$$.

For each testcase, you should output one line containing one integer: the minimum danger for the corresponding query. The answer is guaranteed to fit in a 64 bits number.

8 25 2 20 2 3
10 10
8 7
9 11
13 8
12 10
20 10
22 11
19 9
1 6
1 8
3 4
2 7
3 8

0
82
82

Note that houses 1 - 5 are all "safe" houses since each house has at least 2 neighbours within distance 25. In fact, it is possible to get from every house to every other house with 0 danger. Similarly, houses 6 - 8 are also safe houses and mutually reachable.

The cost of getting from house $$$2$$$ to house $$$4$$$ is 0 since it is possible to get from house $$$2$$$ to its safe neighbour house $$$1$$$ and then from house $$$1$$$ to its neighbour house $$$4$$$.

Getting from house $$$2$$$ to house $$$7$$$ optimally can be done by going from house $$$2$$$ to house $$$1$$$ with a cost 0, then going from house $$$1$$$ to house $$$8$$$ with a $$$82$$$ cost using a forest road and then finally going from house $$$8$$$ to its safe neighbour house $$$7$$$. The maximum on this path is $$$82$$$.

Getting from house $$$3$$$ to house $$$8$$$ can be done by going to house $$$1$$$ with cost 0 and from house $$$1$$$ to house $$$8$$$ with cost $$$82$$$.