철도 요금

JOI 국에는 도시가 $N$개 있고, 각 도시에 $1$부터 $N$까지 번호가 붙어 있다. 도시 $1$은 JOI 국의 수도이다.

JOI 국에는 철도 회사가 하나뿐이고, 이 회사는 노선 $M$개를 운행한다. 노선에는 $1$부터 $M$까지 번호가 붙어 있으며, $i$번 노선($1 \le i \le M$)은 도시 $U_i$와 도시 $V_i$를 양방향으로 잇는다. 도시 사이를 철도가 아닌 방법으로 이동할 수는 없다. 또 어느 도시에서 어느 도시로든 노선을 몇 번 갈아타면 이동할 수 있다.

지금은 모든 노선의 요금이 1엔이다. 경영이 어려워진 철도 회사는 앞으로 $Q$년에 걸쳐 일부 노선의 요금을 올리는 계획을 세웠다. 계획을 시작한 뒤 $j$년째($1 \le j \le Q$) 연초에 노선 $R_j$의 요금을 1엔에서 2엔으로 올린다. 한 번 오른 요금은 그 뒤로 계속 2엔이고, 다시 오르지 않는다.

이 회사는 해마다 각 도시 주민의 만족도를 조사한다. 계획을 시작하기 전에는 모든 도시의 주민이 회사에 만족하지만, 요금 인상 때문에 불만을 품는 주민이 생길 수 있다.

각 해의 만족도 조사는 그해 요금 인상을 마친 뒤에 한다. 따라서 $j$년째 조사는 노선 $R_1, R_2, \dots, R_j$의 요금만 오르고 나머지 노선의 요금은 그대로인 상태에서 이루어진다. $j$년째 조사에서 도시 $k$($2 \le k \le N$)의 주민은 다음 조건이 성립할 때, 그리고 그때만 회사에 불만을 품는다.

• 그 시점의 요금으로 도시 $k$에서 수도인 도시 $1$까지 이동하는 최소 비용이, 계획을 시작하기 전 요금으로 도시 $k$에서 도시 $1$까지 이동하는 최소 비용보다 크다.

노선 몇 개를 갈아타서 이동할 때의 비용은 사용한 노선의 요금을 모두 더한 값이다. 도시 $1$의 주민은 회사에 불만을 품지 않는다. 요금이 오른 뒤 최소 비용을 내는 경로는 계획을 시작하기 전 최소 비용을 내는 경로와 다를 수 있다는 점에 주의하시오.

철도 노선 정보와 요금 인상 계획이 주어질 때, 각 해의 만족도 조사에서 불만을 품는 주민이 있는 도시의 수를 구하는 프로그램을 작성하시오.

표준 입력으로 다음 정보가 주어진다.

• 첫째 줄에 정수 $N$, $M$, $Q$가 공백으로 구분되어 주어진다. JOI 국에 도시가 $N$개, 노선이 $M$개 있고 요금 인상 계획이 $Q$년에 걸쳐 진행된다는 뜻이다.
• 이어지는 $M$개 줄 중 $i$번째 줄($1 \le i \le M$)에 정수 $U_i$, $V_i$가 공백으로 구분되어 주어진다. $i$번 노선이 도시 $U_i$와 도시 $V_i$를 잇는다는 뜻이다.
• 이어지는 $Q$개 줄 중 $j$번째 줄($1 \le j \le Q$)에 정수 $R_j$가 주어진다. 계획 $j$년째에 노선 $R_j$의 요금을 올린다는 뜻이다.

표준 출력으로 $Q$개 줄을 출력한다. $j$번째 줄($1 \le j \le Q$)에 $j$년째 만족도 조사에서 불만을 품는 주민이 있는 도시의 수를 출력한다.

• $2 \le N \le 100\,000$
• $1 \le Q \le M \le 200\,000$
• $1 \le U_i \le N$ ($1 \le i \le M$)
• $1 \le V_i \le N$ ($1 \le i \le M$)
• $U_i \ne V_i$ ($1 \le i \le M$)
• $1 \le R_j \le M$ ($1 \le j \le Q$)
• $R_j \ne R_k$ ($1 \le j < k \le Q$)
• 어떤 두 도시를 직접 잇는 노선은 최대 한 개이다.
• 모든 도시에서 도시 $1$까지 노선을 사용해 이동할 수 있다.