問題文

はむへいくんの新しいクラスには$1 \sim N$で表される$N$人が所属しています。このクラス内の既存の友好関係は以下のような$M$個の情報によって表現されます。

• $p_i$さんと$q_i$さんは友達である。$(1 \leqq i \leqq M)$

• まだ友達でないような人のペア$(a, b)$を考える。$a$さんとも$b$さんとも友達である人が存在するとき、その日が終わると$a$さんと$b$さんは友達になる。
• 友達の関係が解消されることはない。

入力

$N\ M$
$p_1 q_1$
.
.
.
$p_M q_M$
$Q$
$A_1$
.
.
.
$A_Q$

$1 \leqq N \leqq 10^5$
$0 \leqq M \leqq \min((N * (N-1))/2, 10^5)$

$i(1 \leqq i \leqq M)$について
$1 \leqq p_i < q_i \leqq N$

$i \neq j$なら
$(p_i, q_i) \neq (p_j, q_j)$

$1 \leqq Q \leqq 30$
$1 \leqq A_i \leqq N (1 \leqq i \leqq Q)$

出力

答えを$Q$行出力してください。$i$行目には$i$人目$(A_i)$の答えを出力してください。
具体的には$i$行目には
$i$番目の人$A_i$が友達にできる最大の人数、その人数が初日を0日目として何日目に達成できるかを空白区切りに出力してください。

サンプル

2 1
1 2
2
1
2

1 0
1 0

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

3 2
3 1
3 1
3 2
0 0

18 13
1 2
3 4
4 5
6 7
7 8
8 9
9 10
11 12
12 13
13 14
14 15
15 16
16 17
4
1
3
6
11

1 0
2 1
4 2
6 3