JOI 国有 $N$ 个城市，编号为 $1, 2, \dots, N$。城市 $1$ 是 JOI 国的首都。

此外，JOI 国只有一家铁路公司，该公司运营着 $M$ 条铁路线。这些线路分别编号为 $1, 2, \dots, 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$ 年 ($1 \le j \le Q$) 的满意度调查是在线路 $R_1, R_2, \dots, R_j$ 的票价已经上调，而其他线路票价尚未上调的状态下进行的。在第 $j$ 年 ($1 \le j \le Q$) 的满意度调查中，城市 $k$ ($2 \le k \le N$) 的居民当且仅当满足以下条件时，会对铁路公司感到不满：

• 当前票价下，从城市 $k$ 到首都城市 $1$ 的最小费用，大于计划开始前从城市 $k$ 到城市 $1$ 的最小费用。

注意，使用若干条线路移动时的费用为各线路票价之和。此外，城市 $1$ 的居民不会对铁路公司感到不满。请注意，涨价后实现最小费用的路径，可能与计划开始前实现最小费用的路径不同。

在执行计划之前，我们希望计算出未来 $Q$ 年内，每年满意度调查中对铁路公司感到不满的居民所在的城市数量。

题目描述

给定 JOI 国的铁路线路信息和票价上涨计划，编写一个程序，求出在每次满意度调查中，对铁路公司感到不满的居民所在的城市数量。

输入格式

从标准输入读取以下内容：

• 第 $1$ 行包含 $3$ 个整数 $N, M, Q$，以空格分隔。这表示 JOI 国有 $N$ 个城市和 $M$ 条线路，票价上涨计划跨度为 $Q$ 年。
• 接下来的 $M$ 行中的第 $i$ 行 ($1 \le i \le M$) 包含 $2$ 个整数 $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 \neq V_i$ ($1 \le i \le M$)
• $1 \le R_j \le M$ ($1 \le j \le Q$)
• $R_j \neq R_k$ ($1 \le j < k \le Q$)
• 任意两个城市之间直接相连的线路不超过 $1$ 条。
• 任意城市都可以通过若干条线路到达城市 $1$。

子任务

子任务 1 [12 点] 满足以下条件： $N \le 100$ $M \le 4\,950$ * $Q \le 30$

子任务 2 [14 点] * 满足 $Q \le 30$。

子任务 3 [35 点] * 正确输出中出现的整数种类不超过 $50$ 种。

子任务 4 [39 点] 没有额外限制。

样例

样例 1

输入 1

5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3

输出 1

0
2
2
4
4

说明

在该输入样例中，计划开始前及各次满意度调查时，各城市到城市 $1$ 的费用如下表所示：

例如，在第 $3$ 年的满意度调查中，城市 $3$ 和城市 $5$ 的居民感到不满，因此输出的第 $3$ 行为 $2$。

样例 2

输入 2

4 6 6
1 2
1 3
1 4
2 3
2 4
3 4
1
4
2
5
3
6

输出 2

1
1
2
2
3
3

样例 3

输入 3

2 1 1
1 2
1

输出 3

1