travel — IATI senior
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 25
Algorithms: simulation, modular arithmetic, graph traversal, tree

# Task A4. Travel

![](_page_0_Picture_1.jpeg)

1 sec. 512 MB

Yan enjoys travelling around the country of Iatiland in his car.

Since Yan has been travelling for a long time, he has come up with a description of the map of the whole country. The cities in Iatiland are numbered from 1 to $N$, and there are bi-directional direct roads connecting pairs of different cities. For each city, he has a list of cities that are reachable from it using a direct road. It is guaranteed that there is a unique path between every pair of cities. Note that the path may not be direct, i.e., it may use several direct roads. Notice that this means that there are a total of $N - 1$ direct roads.

Yan likes travelling systematically, so he came up with an algorithm he will follow whilst going around the country.

He starts his journey in city 1 on day 1, and every subsequent day he will follow a direct road from the city he is currently in. The road he chooses is always the first road in the list of the current city. However, this simple procedure seemed pretty boring to Yan, so after picking the road he will next travel on, he removes it from the beginning of the list and appends it to the end.

Yan's main objective for travelling is to meet his friends and gossip with them. He has $M$ friends he wants to visit, numbered from 1 to $M$, and each friend $i$ lives in the city $P_i$. He can visit friend $i$ only when he is currently in city $P_i$. Additionally, Yan wants to visit his friends in the given order, i.e., he cannot visit friend $i + 1$ before visiting friend $i$.

Help Yan find the minimal number of days before he visits all of his friends in the correct order.

## Input

The first line of the standard input contains 2 numbers - $N$ and $M$.

This is followed by $N$ lines, where on line $i$, there are given $k_i$ - the number of direct paths coming out of city $i$, followed by $k_i$ numbers - the initial list of cities to which city $i$ is connected by a direct path.

Following are $M$ numbers on one line - $P_i$, the cities where Yan's friends live.

## Output

Output the required minimum number of days on a single line on the standard output.

## Constraints

*   $1 \le N \le 5 * 10^5$
*   $1 \le M \le 5 * 10^5$
*   $1 \le k_i \le N - 1$
*   $1 \le P_i \le N$

![](_page_1_Picture_1.jpeg)

**XV INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS**
**SHUMEN 2024**

## Subtasks

| Subtask | Points | $N$           | $M$           | Additional constraints |
| :------ | :----- | :------------ | :------------ | :--------------------- |
| 1       | 10     | $\le 50$     | $\le 50$     | None                   |
| 2       | 10     | $\le 1000$   | $\le 1000$   | None                   |
| 3       | 20     | $\le 10^5$    | $\le 1000$   | None                   |
| 4       | 10     | $\le 1000$   | $\le 10^5$    | None                   |
| 5       | 15     | $\le 5 * 10^5$ | $\le 5 * 10^5$ | $P_i = 1$              |
| 6       | 20     | $\le 10^5$    | $\le 10^5$    | None                   |
| 7       | 15     | $\le 5 * 10^5$ | $\le 5 * 10^5$ | None                   |

*Points for a given subtask are awarded only if all tests specified for it are successfully passed.*

## Example

| Input     | Output | Explanation                                                                                                                               |
| :-------- | :----- | :---------------------------------------------------------------------------------------------------------------------------------------- |
| 4 4       | 9      | Yan's journey will take 9 days to pass<br>through the cities 1, 2, 1, 3, 1, 2, 1, 3, 4 in<br>that sequence.                               |
| 2 2 3     |        |                                                                                                                                         |
| 1 1       |        | He will meet friend 1 on the second day,                                                                                                   |
| 2 1 4     |        | friend 2 on the third day, friend 3 on the<br>fifth day, and friend 4 on the ninth day.                                                    |
| 1 3       |        |                                                                                                                                         |
| 2 1 1 4   |        |                                                                                                                                         |

Starter code: