Counting Pairs

Time limit4sMemory limit256 MB

Summary

Given an undirected multigraph with self-loops, count pairs of vertices whose combined incident-edge count exceeds k for each of up to 10^6 queries.

Level: Hard8 of 10
Topics: Graph, Sorting, Prefix sum, Two pointers
Solved: No attempts yet

Problem

You are given an undirected graph $G$ with $N$ vertices, numbered from $1$ to $N$ , and $M$ edges.

Consider a pair of vertices $(a, b)$ with $a < b$ . The incidence of $(a, b)$ is the total number of edges that have at least one endpoint equal to $a$ or $b$ .

You have to answer $Q$ queries. Each query gives an integer $k$ and asks how many pairs of vertices $(a, b)$ in $G$ satisfy $a < b$ and have incidence strictly greater than $k$ .

Input

The first line contains two integers $N$ and $M$ , the number of vertices and the number of edges ( $1 \le N, M \le 10^6$ ).

The next $M$ lines follow. The $i$ -th of them contains two integers $x_i$ and $y_i$ , the endpoints of the $i$ -th edge ( $1 \le x_i, y_i \le N$ ). There may be self-loops or parallel edges.

The next line contains one integer $Q$ , the number of queries ( $1 \le Q \le 10^6$ ).

The next $Q$ lines follow. The $i$ -th of them contains an integer $k_i$ , the $i$ -th query ( $1 \le k_i \le 10^6$ ).

Output

For each query, print a single line with a single integer: the answer to the query.

Examples1

Example 1
Input
```
4 5
1 2
2 4
1 3
2 3
2 1
2
2
3
```
Expected output
```
6
5
```