Farmer John has N (2≤N≤2⋅10⁵) tractors, where the ith tractor can only be used within the inclusive interval [ℓi, ri]. The tractor intervals have left endpoints ℓ₁<ℓ₂<⋯<ℓ_N and right endpoints r₁<r₂<⋯<r_N. Some of the tractors are special.

Two tractors i and j are said to be adjacent if [ℓ_i, r_i] and [ℓ_j, r_j] intersect. Farmer John can transfer from one tractor to any adjacent tractor. A path between two tractors a and b consists of a sequence of transfers such that the first tractor in the sequence is a, the last tractor in the sequence is b, and every two consecutive tractors in the sequence are adjacent. It is guaranteed that there is a path between tractor 1 and tractor N. The length of a path is the number of transfers (or equivalently, the number of tractors within it minus one).

You are given Q (1≤Q≤2⋅10⁵) queries, each specifying a pair of tractors a and b (1≤a<b≤N). For each query, output two integers:

- The length of any shortest path between tractor a to tractor b.

- The number of special tractors such that there exists at least one shortest path from tractor a to tractor b containing it.

#5475 upload 15 done 1 how_to_reg 1

Tractor Paths timer 4s memory 512MB

#5475

Tractor Paths 4s 512MB