In Premiernation, there are cities, with people in the -th city. roads currently connect the cities. These roads are structured in such a way that if they were all bidirectional, there would exist a single unique path connecting any pair of cities. Sadly, these roads are unidirectional. Adding onto the sadness, the main form of communication in Premiernation comes in the form of trucking around piles of SSDs. A communication **connection** can exist between two distinct people and if it is possible to travel from the city lives in to the city lives in using only the roads that exist in Premiernation. You have been given the *roadrollifier*, a tool which can convert a unidirectional road to a bidirectional road. However, since the roadrollifier is a one-time-use item (and thus can only convert one road), the Premier wishes to maximize the social benefits of using it.

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

#### Constraints

For all subtasks,

##### Subtask 1 [20%]

##### Subtask 2 [80%]

No additional constraints.

#### 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 exists 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 Input 2

Without using the roadrollifier, the amount 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.

## Comments