Flashing Lights


Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Python, Rust

YOU: "How do you feel about how the night went?"

JAMIE: "Oh, it was the worst! I had this amazing setlist planned, right? Just total peak. Then Kevin tells me it all needs to change. Says my taste is 'too niche' for the crowd. They just don't know ball! They have zero ball knowledge, and now that's my problem?"

YOU: "How long did it take you to come up with a new setlist?"

JAMIE: "All afternoon! Do you know what it's like deconstructing something like a setlist? It's violence. Cultural violence."

YOU: "So you were stuck at your DJ booth all afternoon?"

JAMIE: "Pretty much. It was just a rush of tuning, rebuilding, tuning, and rebuilding. I was a bit scared I wouldn't get everything done in time! Gleb dropped a crate off at some point. Rory came by too, I think he said something to me? Honestly, I had headphones on. He kind of hovered and left."

Jamie is preparing a light show to accompany his DJ set at the ACPC ball. The show uses n LEDs connected by wires in the shape of a rooted tree. LED 1 is connected to the wall and is the root. Every other LED has exactly one parent LED.

Before the show, Jamie has noticed that k of the LEDs are broken and need to be checked by maintenance. To call maintenance, Jamie selects some simple path from the root of the tree to one of its leaves. Then, maintenance will check every LED on this path including both endpoints.

Jamie can call maintenance multiple times, making them check LEDs on multiple different paths through the tree. However, he wants to bother maintenance as little as possible. What is the minimum number of paths Jamie he needs to select, to ensure all broken LEDs are checked at least once?

Input

The first line contains two integers n and k (2 \leq n \leq 3 \times 10^4, 1 \leq k \leq n), the number of LEDs in the tree, and the number of broken LEDs. The LEDs are labeled 1 through to n with 1 being the root.

The next line contains n-1 space-separated integers p_2,\dots,p_n (1 \leq p_i \leq n, p_i \neq i), the parent of each LED. Notice that LED 1 has no parent, so the first integer here is the parent of LED 2. This is guaranteed to form a valid rooted tree with root 1.

The next line contains k space-separated integers a_1,\dots,a_k (1 \leq a_i \leq n). Each integer represents the label of a broken LED. The integers in this line are guaranteed to be unique and strictly increasing.

Output

Output a single integer, the minimum number of paths that Jamie must select for maintenance to check, so that all broken LEDs are checked.

Example

Input 1
5 2
1 1 2 2
2 4
Output 1
1

The tree looks as follows:

    1
   / \
  2*  3
 / \
4*  5

If Jamie selects tbe path 4 \rightarrow 2 \rightarrow 1, both broken LEDs are checked, so one path is enough.

Input 2
6 3
5 5 1 1 4
2 3 4
Output 2
3

The tree looks as follows:

    1
   / \
  5   4*
 / \   \
2*  3*  6

LEDs 2, 3 and 6 are broken, but no two lie on the same path from the root. Therefore, Jamie must select three paths to cover all of them:

  • 1 \to 5 \to 2
  • 1 \to 5 \to 3
  • 1 \to 4 \to 6

Comments

There are no comments at the moment.