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.