#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
int spreadInfection(vector<vector<int>>& adj, vector<int>& malware, int removeNode = -1) {
    int n = malware.size();
    vector<int> infected(n, 0);
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (malware[i] == 1 && i != removeNode) {
            q.push(i);
            infected[i] = 1;
        }
    }
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : adj[node]) {
            if (infected[neighbor] == 0 && neighbor != removeNode) {
                infected[neighbor] = 1;
                q.push(neighbor);
            }
        }
    }
    int totalInfected = 0;
    for (int i = 0; i < n; i++) {
        if (infected[i] == 1) totalInfected++;
    }

    return totalInfected;
}
int minimizeMalwareSpread(int g_nodes, vector<int>& g_from, vector<int>& g_to, vector<int>& malware) {
    vector<vector<int>> adj(g_nodes);
    for (int i = 0; i < g_from.size(); i++) {
        adj[g_from[i] - 1].push_back(g_to[i] - 1); 
        adj[g_to[i] - 1].push_back(g_from[i] - 1);
    }
    int baselineInfection = spreadInfection(adj, malware);
    int bestNode = -1;
    int minInfected = baselineInfection;
    for (int i = 0; i < g_nodes; i++) {
        if (malware[i] == 1) {
            int infectedCount = spreadInfection(adj, malware, i);
            if (infectedCount < minInfected || (infectedCount == minInfected && (bestNode == -1 || i < bestNode))) {
                minInfected = infectedCount;
                bestNode = i;
            }
        }
    }

    return bestNode + 1; 
}

int solve(vector<int>& arr, int x) {
    int n = arr.size();
    int total = accumulate(arr.begin(), arr.end(), 0);
    int target = total - x;
    
    if (target < 0) return -1;
    if (target == 0) return n;

    int maxi = -1, curr = 0;
    unordered_map<int, int> pm;
    pm[0] = -1; 

    for (int i = 0; i < n; ++i) {
        curr += arr[i];
        
        if (pm.find(curr - target) != pm.end()) {
            maxi = max(maxi, i - pm[curr - target]);
        }
        
        pm[curr] = i;
    }

    return maxi == -1 ? -1 : n - maxi;
}

import math

def getDataDependenceSum(n):
    m = int(math.isqrt(n))
    maxSmallX = n // m
    sumSmallX = (maxSmallX * (maxSmallX + 1)) // 2
    myst1c = sumSmallX
    for k in range(1, m + 1):
        x = n // k
        if x > maxSmallX:
            myst1c += x
    return myst1c

import java.util.TreeSet;
public class Main {
    public int TaichiAndLand(int n, int m, int[][] arr, int K) {
        int maxSum = Integer.MIN_VALUE;
        for (int top = 0; top < n; top++) {
            int[] columnSum = new int[m];
            for (int bottom = top; bottom < n; bottom++) {
                for (int col = 0; col < m; col++) {
                    columnSum[col] += arr[bottom][col];
                }
                maxSum = Math.max(maxSum, solve(columnSum, K));
            }
        }

        return maxSum;
    }
    private int solve(int[] nums, int K) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        TreeSet<Integer> cc = new TreeSet<>();
        cc.add(0);

        for (int num : nums) {
            sum += num;
            Integer prefix = cc.ceiling(sum - K);
            if (prefix != null) {
                maxSum = Math.max(maxSum, sum - prefix);
            }

            cc.add(sum);
        }

        return maxSum;
    }

import java.util.*;
public class Main {
    static class DSU {
        int[] parent, size;
        public DSU(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;   
            }
        }
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); 
            }
            return parent[x];
        }
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (size[rootX] < size[rootY]) {
                    parent[rootX] = rootY;
                    size[rootY] += size[rootX];
                } else {
                    parent[rootY] = rootX;
                    size[rootX] += size[rootY];
                }
            }
        }
    }
    public static int solution(int n, int p, int[][] programmers) {
        DSU dsu = new DSU(n);
                for (int i = 0; i < p; i++) {
            int u = programmers[i][0];
            int v = programmers[i][1];
            dsu.union(u, v);
        }
        Map<Integer, Integer> componentSize = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = dsu.find(i);
            componentSize.put(root, componentSize.getOrDefault(root, 0) + 1);
        }
        long totalPairs = (long) n * (n - 1) / 2;
                for (int size : componentSize.values()) {
            totalPairs -= (long) size * (size - 1) / 2;
        }

        return (int) totalPairs;
    }