Problem Statement

Hamuhei's new class has $N$ members, numbered $1 \sim N$. The existing friendships in this class are represented by the following $M$ pieces of information.

• Person $p_i$ and person $q_i$ are friends. $(1 \leqq i \leqq M)$

• Consider a pair of people $(a, b)$ who are not yet friends. If there exists a person who is friends with both $a$ and $b$, then $a$ and $b$ become friends at the end of that day.
• A friendship is never dissolved.

Input

$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)$

For $i(1 \leqq i \leqq M)$
$1 \leqq p_i < q_i \leqq N$

If $i \neq j$, then
$(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)$

Output

Output the answers in $Q$ lines. On the $i$-th line, output the answer for the $i$-th person $(A_i)$.
Specifically, on the $i$-th line,
output, separated by a space, the maximum number of people that the $i$-th person $A_i$ can become friends with, and the day on which that number can be achieved, where the first day is counted as day 0.

Sample

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