Answer whether each pair of vertices is connected in an undirected graph.

Input

The first line contains n and m, followed by m edges. The next line contains q, followed by q query pairs s t.

• 1 <= n <= 1000
• 1 <= q <= 10000

Output

For each query, print 1 when a path exists and -1 otherwise.

Example

Input

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

Output

1
-1
1