题目描述

小胖赛阿罗和小瘦伊丸一起看武侠电视剧，一起讨论剧情，江湖武林帮派众多，多年之后出现了帮派合并的问题，现在有 $n$ 个人，编号 从 $1$ 到 $n$，有 $m$ 组关系，每组关系给出两个编号 $a$ 和 $b$，表示 $a$ 和 $b$ 是同门，小瘦伊丸了解这个帮派关系后，小胖赛 阿罗问小瘦伊丸 $q$ 次，每次询问给出编号 $x$，查询 $x$ 所在门派的人数，请你编程帮帮小瘦伊丸解决这个问题吧。

输入格式

第一行输入 n($1 \leq n \leq 5e^4$) 和 m($1 \leq m \leq 10^6$)，表示有 $n$ 个人，$m$ 组关系。

紧接着输入 $m$ 行，每行两个整数 $a$ 和 $b$，表示 $a$ 和 $b$ 是同门。

第 $m+2$ 行输入一个 $q$，表示有 $q$ 组查询。

紧接着输入 $q(1\leq q \leq 10^6)$行，每行两个整数 $x$，查询 $x$ 所在门派的人数。

输出格式

输出 $q$ 行，每组查询输出 $x$ 所在门派的人数。

输入输出样例

8 5
1 7
1 6
1 2
6 4
3 7
4
1
5
6
7

6
1
6
6

说明/提示

对于 $20\%$ 的数据，$1 \leq n, m, q \leq 100$。

对于 $70\%$ 的数据，$1 \leq n \leq 10^4$，$1 \leq m,q \leq 10^5$。

对于 $100\%$ 的数据，$1\leq n \leq 5\times10^4$，$1\leq m，q \leq 10^6$。