You are given an undirected graph defined by an integer n, the number of nodes, and a 2D integer array edges, the edges in the graph, where edges[i] = [ui, vi] indicates that there is an undirected edge between ui and vi. You are also given an integer array queries.

Let incident(a, b) be defined as the number of edges that are connected to either node a or b.

The answer to the jth query is the number of pairs of nodes (a, b) that satisfy both of the following conditions:


	a &lt; b
	incident(a, b) &gt; queries[j]


Return an array answers such that answers.length == queries.length and answers[j] is the answer of the jth query.

Note that there can be multiple edges between the same two nodes.

&nbsp;
Example 1:

Input: n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
Output: [6,5]
Explanation: The calculations for incident(a, b) are shown in the table above.
The answers for each of the queries are as follows:
- answers[0] = 6. All the pairs have an incident(a, b) value greater than 2.
- answers[1] = 5. All the pairs except (3, 4) have an incident(a, b) value greater than 3.


Example 2:

Input: n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]
Output: [10,10,9,8,6]


&nbsp;
Constraints:


	2 &lt;= n &lt;= 2 * 104
	1 &lt;= edges.length &lt;= 105
	1 &lt;= ui, vi &lt;= n
	ui != vi
	1 &lt;= queries.length &lt;= 20
	0 &lt;= queries[j] &lt; edges.length


class Solution:
    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:
        p_c = [0] * (n+1) # point counter
        e_c = defaultdict(int) # edge counter
        
        for a,b in edges:
            p_c[a] += 1
            p_c[b] += 1
            if a<b:
                e_c[(a,b)] += 1
            else:
                e_c[(b,a)] += 1
        
        f_c = defaultdict(int) # frequency of point counter (compress the individual calculations into massive one)
        for i in range(1, n+1):
            f_c[p_c[i]] += 1

        cnt_amt = defaultdict(int) # frequency of same cnt on pairs without edge adjustment
        f_key = list(f_c.keys()) # frequency key
        l_f = len(f_key)
        for i in range(l_f):
            f1 = f_key[i]
            cnt_amt[f1*2] += f_c[f1] * (f_c[f1]-1) // 2 # 3 points with 4, then you get 8 
                                                        # for a frequency of 3 * (3-2) // 2 = 3
            for j in range(i+1, l_f):
                f2 = f_key[j]
                cnt_amt[f1+f2] += f_c[f1] * f_c[f2] # 2 points with 2, 3 points with 4
                                                    # will have 6 with frequency of 2 * 3 = 6
        
        for (u,v), z in e_c.items(): # edge adjustment
            s = p_c[u] + p_c[v]
            t = s - z
            cnt_amt[s] -= 1
            cnt_amt[t] += 1
        
        cnt_keys = sorted(cnt_amt.keys(), key=lambda x: -x) # accumulate the frequency by descending order
        res = defaultdict(int)
        tmp = 0
        for key in cnt_keys:
            if cnt_amt[key]: # if it is 0 then dont bother to keep them
                tmp += cnt_amt[key]
                res[key] = tmp

        res_keys = sorted(res.keys()) # bisection search 
        for i, q in enumerate(queries):
            local = bisect.bisect(res_keys, q)
            try:
                queries[i] = res[res_keys[local]]
            except:
                queries[i] = 0 # some test cases are annoying by requesting an unreasonable large number
        
        return queries
class Solution {
    public int[] countPairs(int n, int[][] edges, int[] queries) {
        Map<Integer, Map<Integer, Integer>> dupMap = new HashMap<>();
        Map<Integer, Set<Integer>> map = new HashMap<>();
        int[] ans = new int[queries.length];
        int[] count = new int[n];
        for (int[] e : edges){
            int min = Math.min(e[0]-1, e[1]-1);
            int max = Math.max(e[0]-1, e[1]-1);
            dupMap.computeIfAbsent(min, o -> new HashMap<>()).merge(max, 1, Integer::sum);
            map.computeIfAbsent(min, o -> new HashSet<>()).add(max);
            count[min]++;
            count[max]++;
        }
        Integer[] indexes = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(indexes, Comparator.comparingInt(o -> count[o]));
        for (int j = 0, hi = n; j < queries.length; j++, hi = n){
            for (int i = 0; i < n; i++){
                while(hi>i+1&&count[indexes[i]]+count[indexes[hi-1]]>queries[j]){
                    hi--;
                }
                if (hi==i){
                    hi++;
                }
                ans[j]+=n-hi;
                for (int adj : map.getOrDefault(indexes[i], Set.of())){
                    int ttl = count[indexes[i]] + count[adj];
                    if (ttl > queries[j] && ttl-dupMap.get(indexes[i]).get(adj) <= queries[j]){
                        ans[j]--;
                    }
                }
            }
        }
        return ans;
    }
}
class Solution {
    vector<int> st;
public:
    void update(int tind,int tl,int tr,int ind,int val){
        if(tl>tr)
            return;
        if(tl==tr){
            st[tind]+=val;
            return;
        }
        int tm=tl+((tr-tl)>>1),left=tind<<1;
        if(ind<=tm)
            update(left,tl,tm,ind,val);
        else
            update(left|1,tm+1,tr,ind,val);
        st[tind]=st[left]+st[left|1];
    }
    
    int query(int tind,int tl,int tr,int ql,int qr){
        if(tl>tr or qr<tl or ql>tr)
            return 0;
        if(ql<=tl and tr<=qr)
            return st[tind];
        int tm=tl+((tr-tl)>>1),left=tind<<1;
        return query(left,tl,tm,ql,qr)+query(left|1,tm+1,tr,ql,qr);
    }
    
    vector<int> countPairs(int n,vector<vector<int>>& a,vector<int>& q) {
        vector<int> f(n+2,0);
        vector<unordered_map<int,int>> mp(n+2); // using a normal map gives TLE
        
        for(auto v:a){
            int mx=max(v[0],v[1]),mn=min(v[1],v[0]);
            f[mx]++;
            f[mn]++;
            mp[mx][mn]++;
        }
        
        vector<int> ans(q.size(),0);
        int m=a.size();
        st.resize(4*m+40,0);
        
        for(int i=n;i;i--){
			// reducing the common edges between current node and its adjacent
            for(auto e:mp[i]){
                update(1,0,m,f[e.first],-1);
                update(1,0,m,f[e.first]-e.second,1);
            }
            
            int curr=f[i];
            for(int j=0;j<q.size();j++)
                ans[j]+=query(1,0,m,max(0,q[j]-curr+1),m);
            
			// reversing the changes made initially
            for(auto e:mp[i]){
                update(1,0,m,f[e.first],1);
                update(1,0,m,f[e.first]-e.second,-1);
            }
            
            update(1,0,m,f[i],1);
        }
        return ans;
    }
};
var countPairs = function(n, edges, queries) {
    const degree = Array(n+1).fill(0)
    const edgesMap = new Map()
    const countMemo = new Map()
    const answer = []
    
    for(let [u, v] of edges) {
        degree[u]++
        degree[v]++
        const key = `${Math.min(u, v)}-${Math.max(u, v)}`;
        edgesMap.set(key, (edgesMap.get(key) || 0) + 1);
    }
    const sortedDegree = [...degree.slice(1)].sort((a, b) => a - b);  
    
    for(let num of queries) {
        let cnt;
        if(countMemo.has(num)) cnt = countMemo.get(num)
        else {
            cnt = calculateCount(num)
            countMemo.set(num, cnt);
        }
        answer.push(cnt)
    }
    
    function calculateCount(num) {
        let low = 0, high = sortedDegree.length-1, cnt = 0;
        
        while(low < high) {
            const sum  = sortedDegree[low] + sortedDegree[high];
            
            if(sum > num) {
                cnt += (high - low);
                high--;
            } else low++;
        }
        
        for(let [key, val] of edgesMap) {
            const [u, v] = key.split('-').map(Number);
            
            if(degree[u] + degree[v] > num) {
                const newSum = degree[u] + degree[v] - val
                if(newSum <= num) cnt--;
            }
        }
        return cnt;
    }
    return answer;
};
Count Pairs Of Nodes