Forest Run

시간 제한6초메모리 제한2048 MB

요약

여러 뿌리에서 시작하는 트리 숲이 주어질 때, 모든 뿌리에서 잎까지의 경로를 왕복하는 데 필요한 총 거리를 구한다.

난이도: 보통10점 중 5점
유형: 트리, DFS
정답자: 아직 제출이 없습니다

문제

Forrest Gump wants to participate in the annual Forest Run. As usual, the forest where this event takes place contains many trees. However, the forest for this year's run is special. The hiking trails are also shaped like trees; this means that each entrance into the forest branches off into multiple trails, these trails will never form a cycle, and entrances into the forest do not have incoming trails from another entrance. In order to finish the Forest Run, every path from every entrance to every trail end and back must be run.

All intersections in the forest (including the entrances) are numbered, starting from one. Every trail between two intersections is one kilometer long. You can neglect the distance between the entrances to the forest.

Can you calculate the full distance that Forrest must run in order to complete the Forest Run?

입력

One line with two integers: $1 \leq n \leq 10^6$ , the number of intersections in the forest, and $1 \leq e \leq n$ , the number of entrances into the forest.
One line with $e$ integers: these are the numbers of the intersections that are the entrances to the forest.
$n$ lines, one for each intersection $i$ . Each line has one integer $0 \leq c\_i \leq n - 1$ , indicating the number of trails exiting intersection $i$ , followed by $c\_i$ integers which are the numbers of the intersections that the trails exiting intersection $i$ lead to.

출력

One line containing one integer, which is the amount of kilometers that Forrest must run.

예제2

예제 1
입력
```
7 1
1
2 2 3
2 4 5
2 6 7
0
0
0
0
```
예상 출력
```
16
```
예제 2
입력
```
6 2
1 5
1 2
2 3 4
0
0
1 6
0
```
예상 출력
```
10
```