23129번 - Counting Pairs 다국어

문제

You are given an undirected graph $G$ consisting of $N$ vertices, numbered from 1ドル$ to $N,ドル and $M$ edges.

Consider a pair of vertices $(a, b),ドル where $a < b$. Let the incidence of $(a, b)$ be the total number of edges with at least one of their endpoints being $a$ or $b$.

You have to answer $Q$ queries. Each query is given as an integer $k,ドル and asks how many pairs of vertices $(a, b)$ are there in $G$ such that $a < b$ and the incidence of $(a, b)$ is strictly greater than $k$.

입력

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

Then $M$ lines follow. The $i$-th of them contains two integers $x_i$ and $y_i,ドル denoting 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 of input contains one integer $Q,ドル the number of queries (1ドル \le Q \le 10^6$).

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

출력

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

제한

힌트