Batyr I and Tima the Great - Ring Road Travel · IZhO 2024 #B

Physics · mechanics

Problem

There is a country that is a large ring road in the shape of a circle. On the ring road there are LL cities evenly spaced at a distance 1 from each other. Neighboring cities on the ring road are connected by roads in the form of arcs. Unfortunately, the greedy King Batyr I has made these roads toll and charges 1 gold coin for travel. But Tima the Great made mm illegal roads that connect two cities in a straight line (chord), ii-th road connects two cities with numbers aia_i and bib_i. Residents can now travel by using both toll roads and free roads. In doing so, residents can change direction at the intersections of the two roads Tima built as many times as they want, and it's still free! You are given qq queries, for the ii-th query determine what is the minimum number of gold coins a resident needs to spend to travel from city xix_i to city yiy_i. Input: The first line of input data contains three integers L,m,qL, m, q (1≤L≤109,0≤m≤105,1≤q≤105)(1 \leq L \leq 10^9, 0 \leq m \leq 10^5, 1 \leq q \leq 10^5) — the number of cities in the country, the number of illegal roads that Tima the Great built, and the number of queries. The next mm lines contain two integers each ai,bia_i, b_i (1≤ai<bi≤L)(1 \leq a_i < b_i \leq L) — the two cities that are connected by the ii-th road. The next qq lines contain two integers each xi,yix_i, y_i (1≤xi,yi≤L)(1 \leq x_i, y_i \leq L) — two cities between which the resident has to travel. Output: Print qq lines, in the ii-th line print the minimum number of gold coins that must be paid to travel from city xix_i to city yiy_i.

Browse the problem library