| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
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 visitng friend $i$.
Help Yan find the minimal number of days before he visits all of his friends in the correct order.
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 the required minimum number of days on a single line on the standard output.
| Subtasks | Points | $N$ | $M$ | Additional constraints |
|---|---|---|---|---|
| 1 | 10 | $≤ 50$ | $≤ 50$ | None |
| 2 | 10 | $≤ 1000$ | $≤ 1000$ | None |
| 3 | 20 | $≤ 10^5$ | $≤ 1000$ | None |
| 4 | 10 | $≤ 1000$ | $≤ 10^5$ | None |
| 5 | 15 | $≤ 5 \times 10^5$ | $≤ 5 \times 10^5$ | $P_i = 1$ |
| 6 | 20 | $≤ 10^5$ | $≤ 10^5$ | None |
| 7 | 15 | $≤ 5 \times 10^5$ | $≤ 5 \times 10^5$ | None |
4 4 2 2 3 1 1 2 1 4 1 3 2 1 1 4
9