2025-ho-t5_Post_Office — JOI JOI
Task type: batch | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 26
Algorithms: greedy, data structures, tree, segment tree, tree decomposition

![](_page_0_Picture_0.jpeg)

# 5 Post Office

In the JOI country, there are *N* post offices, numbered from 1 to *N*. Each post office has an assigned "destination," and the destination of post office *i* is post office *P<sub>i</sub>*. Note that it is possible for *P<sub>i</sub>* = *i*. If a package is sent from post office *i* at time *t*, it will arrive at post office *P<sub>i</sub>* at time *t* + 1. However, a post office cannot send another package while it is in the process of sending a package. Each post office can store an unlimited number of packages at any given time.

Now, *M* packages need to be delivered in the JOI country. The *j*-th package arrives at post office *A<sub>j</sub>* at time 0, and it must eventually be delivered to the assigned post office *B<sub>j</sub>*. Given the information about the post offices and the packages, write a program to determine whether it is possible to deliver all the packages to their assigned post offices, and if so, find the smallest possible time at which the last package arrives at its assigned post office.

### Input

Read the following data from the standard input.

```
N
P1 P2 · · · PN
M
A1 B1
A2 B2
.
.
.
AM BM
```

### Output

Output a single line to the standard output. If it is possible to deliver all the packages to their assigned post offices, output the smallest possible time at which the last package arrives at its assigned post office. Otherwise, output -1 instead.

![](_page_1_Picture_0.jpeg)

## Constraints

*   2 ≤ *N* ≤ 200 000.
*   1 ≤ *M* ≤ 200 000.
*   1 ≤ *P<sub>i</sub>* ≤ *N* (1 ≤ *i* ≤ *N*).
*   1 ≤ *A<sub>j</sub>*, *B<sub>j</sub>* ≤ *N* (1 ≤ *j* ≤ *M*).
*   *A<sub>j</sub>* ≠ *B<sub>j</sub>* (1 ≤ *j* ≤ *M*).
*   Given values are all integers.

## Subtasks

*   (3 points) *N* ≤ 3 000, *M* = 1.
*   (9 points) *N* ≤ 3 000, *M* ≤ 3 000.
*   (13 points) *P* = (1, 1, 2, ..., *N* - 1), and max(*B*<sub>1</sub>, *B*<sub>2</sub>, ..., *B<sub>M</sub>*) < min(*A*<sub>1</sub>, *A*<sub>2</sub>, ..., *A<sub>M</sub>*).
*   (25 points) *P* = (1, 1, 2, ..., *N* - 1).
*   (11 points) *P* = (*N*, 1, 2, ..., *N* - 1).
*   (25 points) *P*<sub>1</sub> = 1, *P<sub>i</sub>* < *i* (2 ≤ *i* ≤ *N*).
*   (14 points) No additional constraints.

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :-------------- |
| 5              | 3               |
| 1 1 2 3 4      |                 |
| 3              |                 |
| 3 2            |                 |
| 3 1            |                 |
| 3 1            |                 |

For example, by sending the packages in the following way, all the packages can be delivered to their assigned post offices by time 3:

*   At time 0, packages 1, 2, and 3 are at post office 3. Send package 2 to post office 2.
*   At time 1, package 2 is at post office 2, and packages 1 and 3 are at post office 3. From post office 2,

![](_page_2_Picture_0.jpeg)

send package 2 to post office 1, and from post office 3, send package 3 to post office 2.

*   At time 2, package 2 is at post office 1, package 3 is at post office 2, and package 1 is at post office 3. From post office 2, send package 3 to post office 1, and from post office 3, send package 1 to post office 2.
*   At time 3, packages 2 and 3 are at post office 1, and package 1 is at post office 2. At this point, all the packages have reached their destinations.

Since it is not possible to deliver all the packages to their assigned post offices by time 2, output 3. This sample input satisfies the constraints of Subtasks 2, 3, 4, 6, 7.

| Sample Input 2 | Sample Output 2 |
| :------------- | :-------------- |
| 3              | -1              |
| 2 1 3          |                 |
| 1              |                 |
| 1 3            |                 |

No matter how the packages are sent, it is impossible to deliver a package from post office 1 to post office 3, so output -1.

This sample input satisfies the constraints of Subtasks 1, 2, 7.

| Sample Input 3 | Sample Output 3 |
| :------------- | :-------------- |
| 7              | 5               |
| 1 1 2 3 4 5 6  |                 |
| 6              |                 |
| 4 2            |                 |
| 5 1            |                 |
| 5 3            |                 |
| 6 2            |                 |
| 7 3            |                 |
| 7 6            |                 |

This sample input satisfies the constraints of Subtasks 2, 4, 6, 7.

![](_page_3_Picture_0.jpeg)

| Sample Input 4 | Sample Output 4 |
| :------------- | :-------------- |
| 4              | 4               |
| 4 1 2 3        |                 |
| 4              |                 |
| 4 1            |                 |
| 4 1            |                 |
| 2 3            |                 |
| 2 3            |                 |

This sample input satisfies the constraints of Subtasks 2, 5, 7.

| Sample Input 5 | Sample Output 5 |
| :------------- | :-------------- |
| 7              | 5               |
| 1 1 1 3 3 4 4  |                 |
| 5              |                 |
| 6 1            |                 |
| 6 3            |                 |
| 7 1            |                 |
| 5 1            |                 |
| 5 1            |                 |

This sample input satisfies the constraints of Subtasks 2, 6, 7.

| Sample Input 6         | Sample Output 6 |
| :----------------------- | :-------------- |
| 11                     | 6               |
| 3 1 2 5 6 7 8 4 4 5 10 |                 |
| 6                      |                 |
| 2 1                    |                 |
| 9 8                    |                 |
| 11 8                   |                 |
| 10 4                   |                 |
| 5 6                    |                 |
| 5 7                    |                 |

This sample input satisfies the constraints of Subtasks 2, 7.

Starter code: