20659번 - 해군

Byteland에는 $N$ 개의 호수가 있으며, 몇 개의 강이 두 호수를 직접 연결하고 있다. 당신은 Byteland의 해군 지휘관으로, 다가오는 전쟁에 대비한 전략을 세우려고 한다.

Byteland의 정보부에서는 다가오는 전쟁이 $T+1$ 일 동안 계속될 것이며, 각 날 사이에 있는 밤마다 전투가 있을 것이라는 첩보를 주었다. 즉, 모든 $1 \le i \le T$ 에 대해서, $i$ 일 과 $i+1$일 사이의 밤에 전투가 이루어 지는 것이다.

Byteland의 호수와 강은 그래프로 생각할 수 있다. 어떠한 강이 제거되었을 때 연결 컴포넌트의 개수가 증가하면, 이 강은 격전지로 분류된다. (그래프 이론에서 이러한 강은 "절선" 이라고 부른다.)

호수에는 항상 물이 차 있지만, 강은 그 때의 날씨에 따라서 물이 빠질 수도 있다. 즉, 어떠한 호수의 쌍이 날씨에 따라 강으로 직접 연결될 수도 있고, 아닐 수도 있다. Byteland에는 $M$ 개 종류의 날씨가 있고, $i$ 번 날씨는 집합 $A_i$ 에 있는 두 호수의 쌍을 강으로 만든다. 

과학자들은 모든 $1 \le i \le T + 1$ 에 대해, $i$일의 낮의 날씨 $B_i$ 를 찾았다. 과학자들은, $i$ 일 과 $i+1$일 사이의 밤에 전투가 이루어 질 때, 강의 집합은 $A_{B_i} \cup A_{B_{i + 1}}$ 이라고 예측했다.

이 예측들을 사용하여, 매 $T$ 번의 전투에서 격전지의 개수를 출력하라.

집합은 같은 원소를 두 개 이상 포함할 수 있으며 (Multiset), 호수와 강이 평면 그래프를 이루지 않을 수 있다.

첫번째 줄에 세 정수 $N, M, T$ 가 주어진다. ($1 \le N, M \le 100\,000, 1 \le T \le 200\,000$)

두번째 줄에 $T+1$ 개의 정수 $B_1, B_2, \ldots, B_{T + 1}$ 이 주어진다. ($1 \le B_i \le M$)

이후 $M$ 개의 줄에 집합 $A_i$ 가 주어진다. 이 집합은 $2K_i + 1$ 개의 정수로 포함된다. 첫 번째 정수는 $A_i$ 의 크기 $K_i$ 이다. 이후 $2K_{i}$ 개의 정수로 해당 날씨에서 강으로 직접 연결되는 두 호수의 번호가 순서대로 주어진다. 두 호수의 번호는 서로 다르다.

$K_i$ 의 합은 $200\,000$ 을 넘지 않는다.

$T$ 개의 줄에 걸쳐 문제의 정답을 출력하라.