Diameter

The country of Dadorlandtiria has \(n\) cities, numbered from \(0\) to \(n-1\). The country also has exactly \(n\) direct roads connecting all the cities. Namely, for every \(0 \le i \le n-1\), cities \(u[i]\) and \(v[i]\) are connected by a direct road.

Notice that all roads in Dadorlandtiria are in need of repair. The country's leader wants to know how inconvenient repairing each road would be for the population.

Specifically, each day some road is closed for repair works. The inconvenience level is defined as the pair of cities between which the travel time is the longest. Note that it may also become impossible to travel between some pairs of cities.

For each road, find the longest travel time in the country after that road is closed. If travel between some cities becomes impossible, return \(-1\) as the answer.

Implementation details

You should implement the following procedure:

int[] find_diameters(int n, int[] u, int[] v)

• \(n\): the total number of cities and roads.
• \(u\), \(v\): arrays of length \(n\) – information about the roads.
• The procedure should return an array of length \(n\), where element \(i\) is the longest travel time after closing road \(i\), or \(-1\).
• This procedure is called exactly once.

Example

Consider the following call:

find_diameters(4, [1, 1, 0, 3], [0, 2, 3, 1])

Initially, Dadorlandtiria looks like this (cities \(0,1,2,3\) with roads \(1\!-\!0\), \(1\!-\!2\), \(0\!-\!3\), \(3\!-\!1\)):

• While road \(0\) is under repair, the longest travel time is \(3\): \(0 \to 3 \to 1 \to 2\).
• While road \(1\) is under repair, travel between cities \(0\) and \(2\) becomes impossible.
• While road \(2\) is under repair, the longest travel time is \(2\): \(3 \to 1 \to 2\).
• While road \(3\) is under repair, the longest travel time is \(3\): \(3 \to 0 \to 1 \to 2\).

Therefore, find_diameters() should return the array \([3, -1, 2, 3]\).

Constraints

• \(3 \le n \le 200\,000\)
• \(0 \le u[i], v[i] \le n-1\) and \(u[i] \neq v[i]\) (for all \(0 \le i < n\))
• No pair \((u[i], v[i])\) appears twice.
• Initially the country is connected, i.e. it is possible to travel between any pair of cities.

Subtasks

1. (3 points) \(u[i] = i\) and \(v[i] = (i+1) \bmod n\) for all \(0 \le i < n\)
2. (9 points) \(n \le 100\)
3. (21 points) \(n \le 2000\)
4. (9 points) \(k \le 2000\), where \(k\) is the number of roads whose answer is not \(-1\).
5. (58 points) No additional constraints.

Sample grader

The sample grader reads the input in the following format:

• line \(1\): \(n\)
• line \(2 + i\) (\(0 \le i < n\)): \(u[i] \; v[i]\)

Suppose find_diameters() returns the array \(r\). The sample grader prints:

• line \(1\): \(r[0] \; r[1] \; \ldots \; r[n-1]\)