## DMOPC '20 Contest 2 P3 - Roadrollification

View as PDF

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem type

As such, the Premier has tasked you with calculating the maximum number of connections that will exist after using the roadrollifier once.

#### Input Specification

The first line will contain , the number of cities in Premiernation.

The next line will contain space-separated integers .

The next lines will each contain two space-separated integers and , denoting that city has a one-way road directed towards city .

#### Output Specification

Output a single number, the maximum number of connections that can exist after one use of the roadrollifier.

#### Sample Input 1

4
4 2 3 4
1 2
2 3
3 4

#### Sample Output 1

106

#### Explanation of Sample Output 1

Initially, there exist connections:

• Each city resident has connections with other city residents, connections with city residents, connections with city residents, and connection with city residents. Since there are city residents, .
• Each city resident has connection with other city residents, connections with city residents, and connections with city residents. Since there are city residents, .
• Each city resident has connections with other city residents and connections with city residents. Since there are city residents, .
• Each city resident has connections with other city residents. Since there are city residents, .

In all, .

It can be shown that using the roadrollifier on the edge connecting city to city results in the greatest number of connection increases - resulting in an extra connections for total connections.

#### Sample Input 2

9
1 2 3 4 5 6 7 8 9
1 2
2 4
2 5
3 2
6 3
5 8
9 5
5 7

#### Sample Output 2

974

#### Explanation of Sample Output 2

Without using the roadrollifier, the number of connections that would exist would be . It can be shown that the roadrollifier should be used on the road connecting city to city , resulting in an increase of connections. , so is the answer to this case.