숲 달리기

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

요약

각 입구에서 모든 트레일 끝점까지 갔다가 돌아오는 총 거리를 구합니다.

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

문제

포레스트 검프는 매년 열리는 숲 달리기 대회에 참가하려고 한다. 대회가 열리는 숲에는 나무가 많고, 올해 등산로도 나무 모양이다. 입구마다 등산로가 여러 갈래로 나뉜다. 등산로는 순환하지 않으며, 다른 입구에서 들어오는 등산로도 없다. 대회를 완주하려면 모든 입구에서 모든 등산로 끝까지 가는 경로를 하나도 빠짐없이 달린 뒤 되돌아와야 한다.

입구를 포함한 숲의 모든 교차점에는 1부터 번호가 붙어 있다. 두 교차점을 잇는 등산로의 길이는 모두 1km이다. 입구 사이의 거리는 계산에 넣지 않는다.

포레스트가 대회를 완주하려면 몇 km를 달려야 하는지 구하라.

입력

첫째 줄에 교차점 수 $n$ 과 입구 수 $e$ 가 주어진다. $1 \leq n \leq 10^6$ , $1 \leq e \leq n$ .

둘째 줄에는 입구에 해당하는 교차점 번호 $e$ 개가 주어진다.

이후 $n$ 개의 줄에 교차점 $i$ 마다 한 줄씩 주어진다. 각 줄은 교차점 $i$ 에서 나가는 등산로 수 $c_i$ ( $0 \leq c_i \leq n-1$ )로 시작하고, 그 뒤에 $c_i$ 개의 교차점 번호가 이어진다. 이 번호들은 등산로가 연결되는 교차점이다.

출력

포레스트가 달려야 하는 총 거리(km)를 정수 하나로 한 줄에 출력한다.

예제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
```