There are cities in JOI Kingdom, which are indexed by the numbers from
to
. City
is the capital city. Each city has a value called liveliness and the initial value of liveliness of city
is
. Roads in JOI Kingdom connect two different cities bidirectionally. Initially, there are no roads in JOI Kingdom. You have planned
constructions of roads. The
-th construction
is planned to be done in the following way.
- Two cities,
and
, are appointed, when one can go from city
to city
and cannot go from city
to city
by using only roads constructed at that time.
- You construct a road connecting city
and city
. The cost of this construction is the number of pairs of cities
satisfying the following conditions: City
and City
lie on the shortest path between city
and city
, and when one goes from city
to city
he arrives city
before city
, and the value of liveliness of city
is strictly larger than that of city
. Here, cities lying on the path between city
and city
include city
and city
. Notice that the shortest path between city
and city
is unique.
- The values of liveliness of all cities lying on the path between city
and city
change to the value of liveliness of city
.
You want to know the cost of each construction.
Input Specification
The first line of input contains an integer . This means there are
cities in JOI Kingdom.
The second line of input contains space separated integers
. This means the initial value of liveliness of city
is
.
Each of following lines contains two space separated integers
,
. This means city
and city
are appointed for the
-th construction of road. By using roads constructed before the
-th construction, one can go from city
to city
and cannot go from city
to city
.
Output Specification
Output lines to the standard output. The
-th line
of output contains the cost of the
-th construction of road.
Constraints
All input data satisfy the following conditions.
- By using roads constructed before the
-th construction, one can go from city
to city
and cannot go from city
to city
.
Subtask | Points | Additional constraints |
---|---|---|
Sample Input 1
5
1 2 3 4 5
1 2
2 3
2 4
3 5
Sample Output 1
0
0
0
2
Explanation for Sample 1
In Sample Input 1, constructions are done as follows:
- In the first construction, there are no pairs
satisfying the conditions, so the cost is 0. A road connecting city 1 and city 2 is constructed and the value of liveliness of city 1 changes to 2.
- In the second construction, there are no pairs
satisfying the conditions too, so the cost is 0. A road connecting city 2 and city 3 is constructed and the values of liveliness of city 1 and city 2 change to 3.
- In the third construction, there are no pairs
satisfying the conditions too, so the cost is 0. A road connecting city 2 and city 4 is constructed and the values of liveliness of city 1 and city 2 change to 4.
- In the fourth construction, two pairs
satisfy the conditions, so the cost is 2. A road connecting city 3 and city 5 is constructed and the values of liveliness of city 1, city 2 and city 3 change to 5.
Sample Input 2
10
1 7 3 4 8 6 2 9 10 5
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10
Sample Output 2
0
0
0
1
1
0
1
2
3
Comments