시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB0000.000%

문제

Just, Inc. is a huge international company that owns $N$ bank accounts in various countries. The accounts are linked by $N - 1$ direct channels such that it is possible to transfer money from any account to any other account either directly or through intermediate accounts.

If two accounts are linked by a direct channel, a transfer takes an evening to complete. If there is no direct channel, the transfer will involve intermediate accounts and thus it will take multiple days for funds to reach their destination.

External Revenue Service (ERS) suspects that Just is evading taxes, therefore it plans to investigate all the accounts that belong to the company. The investigation will be performed as follows:

  1. On the morning of the first day, ERS will investigate the account No. 1:
    • If there is 1 gigadollar in the account, Just will immediately have to pay taxes.
    • If there are 2 or more gigadollars, the CEO will be charged with forgery and imprisoned. There is no way Just would allow for this to happen
    • If the account is empty, Just will not yet have to pay taxes after the investigation of this account.
  2. On the evening of the first day, Just will send a non-negative integer amount of gigadollars through each of the channels in either direction. However, Just cannot transfer money to or from the account which was investigated earlier on the same day (i.e. No. 1).
  3. On the morning of the second day, ERS will investigate one of the accounts that is linked via a direct channel with the previously investigated account – No. 1. The account is processed in the same way as described above. Just has no idea as to which account ERS will choose.
  4. On the evening of the second day, Just will make new transfers. As before, the account which was just investigated cannot be used.
  5. The investigations of accounts will continue on the third and further days until ERS decides that it has performed enough investigations.

Just is well aware of the investigation procedure. It plans on transferring money between accounts every day in such a way that the money would not be detected for as long as possible and that the company would never be charged with forgery. However, Just does not know which accounts ERS will be choosing and how many investigations will take place, so it must prepare for the worst possible scenario. In other words, Just will transfer money in such a way that no matter what ERS does, the company will not be charged with forgery and will postpone paying taxes the first time as far as possible.

On the morning of the first day there is 1 gigadollar in $M$ different accounts. The rest of the accounts are empty.

Write a program that finds the earliest day on which Just will have to pay taxes for the first time, assuming it transfer money between accounts in an optimal way.

입력

The first line contains two integers $N$ (number of accounts) and $M$ (number of accounts that contain 1 gigadollar at the beginning).

The next $N - 1$ lines contain integers $s_1, s_2, \dots, s_{N-1}$ (one integer per line). $s_i$ ($1 ≤ s_i ≤ i$) denotes that there is a direct channel between accounts $(i + 1)$ and $s_i$.

The last line contains $M$ distinct integers – the list of account numbers that have one gigadollar at the beggining.

출력

Output one integer – the number of day when Just will have to pay the taxes for the first time.

제한

  • $1 ≤ N ≤ 200\,000$
  • $1 ≤ M ≤ N$

서브태스크

번호배점제한
110

$s_i = i$

222

$M = 1$

339

$N ≤ 5\,000$

429

No additional constraints

예제 입력 1

7 2
1
2
3
3
5
6
3 4

예제 출력 1

5

The worst case is illiustrated in the first picture.

If, however, on the fourth evening Just had sent two gigadollars to the account No. 7, on the fifth morning ERS would have found the sixth account empty, but on the sixth day would have found an account with two gigadollars and Just would have been charged with forgery.

The first morning 1st evening 2nd evening 3rd evening 4th evening 5th evening
ERS checked the account No. 1. Just trasnfered 1 gigadollar from account No. 4 to the account No. 3. ERS checked the account No. 2. Just transferred two gigadollars from the account No. 3 to the account No. 5. ERS checked the account No. 3. Just transferred two gigadollars from the account No. 5 to the account No. 6. ERS checked the account No. 5. Just transferred one gigadollar from the account No. 6 to the account No. 7. ERS checked the account No. 6 and found one gigadollar there. Answer: 5th day

Figure 1 Illiustration of the first example

예제 입력 2

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

예제 출력 2

5

If Just sent one gigadollar from the account No. 5 to the account No. 3, money would reach the destination account only in the evening of the second day. However, on the third morning ERS would check the account No. 3 and find this money, so Just will leave one gigadollar in the account No. 5, and ERS will find it on the morning of the fifth day.

예제 입력 3

4 3
1
2
3
2 3 4

예제 출력 3

2

If Just tried to postpone taxes on the second morning, it will be charged with forgery later on (look at Figure 2).

The first morning 1st evening 2nd evening 3rd evening 4th evening
Transfer from account No. 2 to account No. 3. Just tries to postpone the taxes. ERS checks the accout No. 2. In the morning ERS checked the account No. 3 and Just has to pay taxes. The process is not terminated. ERS will check the account No. 4 and charged with forgery.

Figure 2 Illustration of the third example. Bad Just strategy.

채점 및 기타 정보

  • 예제는 채점하지 않는다.