Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

There are N islands and M bridges. The i-th bridge connects the Ai-th and Bi-th islands…

  1. User

    There are N islands and M bridges.

    The i-th bridge connects the A_i-th and B_i-th islands bidirectionally.

    Initially, we can travel between any two islands using some of these bridges.

    However, the results of a survey show that these bridges will all collapse because of aging, in the order from the first bridge to the M-th bridge.

    Let the inconvenience be the number of pairs of islands (a, b) (a < b) such that we are no longer able to travel between the a-th and b-th islands using some of the bridges remaining.

    For each i (1 \leq i \leq M), find the inconvenience just after the i-th bridge collapses.

    Constraints

    • All values in input are integers.
    • 2 \leq N \leq 10^5
    • 1 \leq M \leq 10^5
    • 1 \leq A_i < B_i \leq N
    • All pairs (A_i, B_i) are distinct.
    • The inconvenience is initially 0.

    Input

    Input is given from Standard Input in the following format:

    N M A_1 B_1 A_2 B_2 \vdots A_M B_M

    Output

    In the order i = 1, 2, ..., M, print the inconvenience just after the i-th bridge collapses. Note that the answer may not fit into a 32-bit integer type.

    Examples

    Input

    4 5 1 2 3 4 1 3 2 3 1 4

    Output

    0 0 4 5 6

    Input

    6 5 2 3 1 2 5 6 3 4 4 5

    Output

    8 9 12 14 15

    Input

    2 1 1 2

    Output

    1

  2. DeepSeek Assistant

    We need to solve a problem: There are N islands and M bridges (edges). Initially the graph is fully connected (i.e., we can travel between any two islands using some of these bridges). The bridges collapse in order from 1 to M. After each collapse, we need to compute the inconvenience, defined as the number of unordered pairs (a,b) with a<b that are no longer connected (i.e., not in the same connected component) in the current graph (with the first i bridges removed? Actually after the i-th bridge collapses, that bridge is gone, so we have removed edges 1..i. Initially all bridges are present, inconvenience=0. Then after first collapse (remove edge 1), we compute inconvenience = number of disconnected pairs. After second collapse (remove edges 1 and 2), etc.

    We need output after each removal. So we essentially need to process removals in order, compute number of disconnected pairs after each removal.

    N up to 1e5, M up to 1e5. So we need an efficient method.

    Standard technique: reverse the process, i.e., consider adding edges in reverse order of collapse, starting from no edges (all M bridges collapsed) and adding edges from M down to 1. Initially after all bridges collapsed (i.e., after M-th collapse?), but we need answers after each collapse. So it's easier to compute answers in reverse: start with an empty graph (no edges) after all M bridges have collapsed. The inconvenience at that point is total number of pairs = N*(N-1)/2. Then as we add bridges (from M down to 1), we connect components, decreasing inconvenience. The inconvenience after adding an edge can be computed using union-find and component sizes. When two components of sizes size_u and size_v are merged, the number of newly connected pairs is size_u * size_v. So inconvenience decreases by that amount. So if we start with inconvenience = total pairs and then for each added edge (in reverse order) we compute new inconvenience = prev inconvenience - size_u*size_v (when they were separate). After processing all additions in reverse, we get a sequence of inconvenience values after each addition, which correspond to after each collapse in the original order? Let's carefully map.

    Original timeline: Time 0: all bridges present, inconvenience = 0. After collapse 1 (remove edge 1): graph has edges 2..M, inconvenience = I1. After collapse 2 (remove edges 1,2): inconvenience = I2. ... After collapse M (remove all edges): inconvenience = IM = total pairs = N*(N-1)/2.

    We need output I1, I2, ..., IM.

    If we reverse: Define t = number of edges removed. After all M removed, inconvenience = total_pairs. Now consider adding back edges in reverse order: add edge M, then M-1, ..., 1. After adding edge M (so edges M only, but we will be building cumulative additions), the graph has edges M (since we added the last one first). That's not directly the state after collapse M-1? Let's think:

    State after collapse k: edges k+1, k+2, ..., M are present (since edges 1..k are gone). So it's exactly the graph with edges from k+1 to M.

    Now, consider reverse process: start at state after collapse M (edges none). Then add edge M: state becomes edges M only, which is the state after collapse M-1? No, after collapse M-1, edges M are present? Actually after collapse M-1, edges removed: 1..M-1, so remaining edges: M. So yes, after adding edge M we get exactly state after collapse M-1. Next, add edge M-1: then edges M-1 and M are present, which is state after collapse M-2. So indeed, after adding edges M, M-1, ..., k+1, we have state after collapse k. So the reverse process: we start with inconvenience = total_pairs at state after collapse M. Then for i from M down to 1, we add edge i, and after addition we get state after collapse i-1. So the inconvenience after adding edge i (in reverse order) corresponds to I_{i-1} (where I_0 = 0? Actually I_0 is before any collapse, i.e., initial state with all edges, inconvenience=0; but we don't output that). After adding edge M, we get state after collapse M-1; inconvenience at that point is I_{M-1}. After adding edge M-1, we get state after collapse M-2; inconvenience = I_{M-2}. And so on. After adding edge 1, we get state after collapse 0 (i.e., initial) inconvenience = I_0 = 0.

    So if we process additions in reverse order and compute inconveniences after each addition, we get a sequence of inconveniences: starting from total_pairs (state after collapse M), then after adding M get I_{M-1}, after adding M-1 get I_{M-2}, ..., after adding 1 get I_0=0. So if we reverse that sequence (excluding the initial total_pairs? Actually we need I_1..I_M. Let's see: I_M is after all collapses, which is total_pairs. That's the starting point before any addition. After adding edge M we get I_{M-1}. So I_{M-1} is after first addition. Then after adding edge M-1 we get I_{M-2}. Finally after adding edge 1 we get I_0=0. So the sequence after additions (starting from after addition of M, then after addition of M-1, ..., after addition of 1) is I_{M-1}, I_{M-2}, ..., I_0. To get I_1..I_M, we can take the reverse order: I_M (initial), I_{M-1} (after first addition), ..., I_1 (after addition of edges from M down to 2? Actually after addition of edges M down to 2 yields state after collapse 1. Let's check: after adding edges M, M-1, ..., 2, we have state after collapse 1. So that gives I_1. Then after adding edge 1, we get I_0=0. So indeed, if we process additions from M to 1, we get a sequence of inconveniences: start total_pairs (I_M), then after adding M, we have new inconvenience = I_{M-1}, after adding M-1, I_{M-2}, ..., after adding 2, I_1, after adding 1, I_0=0. So if we output from first to last (i=1..M) in original order, we need I_1, I_2, ..., I_M. The reverse process yields I_M initially, then I_{M-1}, I_{M-2}, ..., I_1, I_0. So we can collect the inconveniences after each addition step, but we need them in increasing order of removals. Actually we need I_1, I_2, ..., I_M. The sequence we get from reverse process (starting state before any addition) is I_M. Then after adding M, we get I_{M-1}. After adding M-1, I_{M-2}. ... After adding 2, I_1. After adding 1, I_0. So if we collect these values in an array in the order they are computed (starting from before any addition), we have [I_M, I_{M-1}, I_{M-2}, ..., I_1, I_0]. Then we can output I_1..I_M by taking the first M elements in reverse order? Let's index: Let ans_rev[k] be inconvenience after k additions? Usually we store an array ans where ans[i] = inconvenience after i removals (i from 0 to M). But we need for i=1..M. So we can compute ans_removal[i] for i=M down to 0? Actually we can compute in reverse order: let cur = total_pairs. We'll have ans[M] = cur. Then for i from M down to 1 (i is the edge we add, but after adding it we get state after removal i-1). So we do: for i = M, M-1, ..., 1: add edge i; cur = cur - size_u*size_v (since new connections reduce inconvenience). After addition, cur corresponds to state after removal i-1. So we can set ans[i-1] = cur. At the end ans[0] = cur (which should be 0). So we can fill ans[0..M] where ans[k] is inconvenience after k removals. Then we output ans[1] through ans[M] in that order.

    That works.

    So algorithm:

    • Read N, M.
    • Store edges list: (A_i, B_i) for i=1..M.
    • Use DSU (Union-Find) with size tracking.
    • Initialize DSU with N nodes, each size=1.
    • cur = N*(N-1)//2 (int, but can be up to ~5e9, need 64-bit). Use long long.
    • ans array of length M+1, ans[M] = cur.
    • Process i from M down to 1:
      • (u, v) = edges[i] (1-indexed, careful).
      • If find(u) != find(v): size_u = size[find(u)], size_v = size[find(v)] cur = cur - size_u * size_v union(u, v)
      • ans[i-1] = cur
    • Then output ans[1], ans[2], ..., ans[M] each on a new line.

    Double-check with examples.

    Example 1: N=4, M=5. Edges: 1:1-2 2:3-4 3:1-3 4:2-3 5:1-4

    Initially all present -> inconvenience 0. After removal 1 (remove 1-2): edges present:2-4, 1-3,2-3,1-4 => graph? Let's compute manually: edges: (3,4), (1,3), (2,3), (1,4). All nodes connected? 1-3-2 and 1-4, and 3-4? Actually 3-4 is present, so all connected => inconvenience 0. So output first line 0 matches.

    After removal 2 (remove 3-4): edges left: (1,3), (2,3), (1,4). Graph: 1 connected to 3 and 4; 2 connected to 3; 3 connected to 1,2; 4 connected to 1. So all 4 nodes are still connected? 2 connects to 3, which connects to 1, and 4 connects to 1, so yes all connected => inconvenience 0. Output second 0.

    After removal 3 (remove 1-3): edges left: (2,3), (1,4). Now components? Let's see: (2,3) forms component {2,3}; (1,4) forms component {1,4}. So two components each size 2. Number of disconnected pairs: total pairs = 6; connected pairs within components: within {2,3}:1 pair; within {1,4}:1 pair; so disconnected = 6 - 2 = 4. So output 4. matches.

    After removal 4 (remove 2-3): edges left: (1,4) only. Then components: {1,4} size2, {2} size1, {3} size1. Connected pairs: within {1,4}:1; others are isolated so no other connections. Disconnected pairs = total pairs 6 - 1 = 5. Output 5. matches.

    After removal 5 (remove 1-4): no edges, all isolated, disconnected pairs = total =6. Output 6. matches.

    Now reverse process: total_pairs = 6. ans[5] = 6 (after all 5 removals). Process i=5: edge 1-4. find(1)!=find(4), size1=1,size4=1 => cur=6-1=5. union. ans[4]=5. i=4: edge 2-3. find(2)!=find(3): sizes 1,1 => cur=5-1=4. union. ans[3]=4. i=3: edge 1-3. find(1) root maybe includes 1,4? After previous unions: after i=5 we have component {1,4} size2; after i=4 we have component {2,3} size2. So find(1) and find(3) are different, sizes 2 and 2 => cur = 4 - 4 =0. union -> component size4. ans[2]=0. i=2: edge 3-4. find(3) root now includes all? Actually after i=3 we have component {1,2,3,4} size4. find(3)=root, find(4)=same root, so no change. cur stays 0. ans[1]=0. i=1: edge 1-2. both in same component, cur stays 0. ans[0]=0. Then output ans[1] to ans[5]: 0,0,4,5,6 matches.

    So works.

    Second example: N=6, M=5. Edges: 1:2-3 2:1-2 3:5-6 4:3-4 5:4-5

    Original connectivity: Let's see after all edges present, it's a tree? Actually edges: (2,3),(1,2),(5,6),(3,4),(4,5) => graph is: 1-2-3-4-5-6, connected all 6. So initial inconvenience 0. After removals in order.

    But our algorithm: total_pairs = 15. Process reverse: ans[5] =15. i=5: edge 4-5? Actually edge5: 4-5. DSU: find(4)!=find(5), sizes1,1 -> cur=15-1=14, union size2. ans[4]=14. i=4: edge 3-4. find(3)!=find(4)? 3 alone, 4 in component with 5 size2? Actually after previous union, component {4,5} size2. find(3) root separate size1. So sizes 1 and 2 => cur=14-2=12. union => component {3,4,5} size3. ans[3]=12. i=3: edge 5-6. find(5) root is component size3; find(6) size1 -> cur=12-3=9. union => component {3,4,5,6} size4. ans[2]=9. i=2: edge 1-2. find(1) size1; find(2) size? There are components: currently we have component A: {3,4,5,6} size4; node 2 alone; node1 alone. find(2) size1, find(1) size1 -> cur=9-1=8? Wait careful: At this point before processing i=2, cur=9 (after i=3). Now we add edge2: (1,2). They are different components of sizes 1 and 1 => cur = 9 - 1 = 8. union -> component size2. ans[1]=8. i=1: edge 2-3. Now we have components: {1,2} size2, {3,4,5,6} size4. find(2) root size2, find(3) root size4 => cur = 8 - 8 = 0? Actually 2*4=8, so cur=8-8=0. union -> size6. ans[0]=0.

    Now ans[1..5] = 8,9,12,14,15? Wait we got ans[1]=8, ans[2]=9, ans[3]=12, ans[4]=14, ans[5]=15. But expected output from example 2: 8,9,12,14,15 (matches). So good.

    Thus the algorithm is correct.

    Now we need to code.

    Constraints: N up to 1e5, M up to 1e5. DSU with path compression and union by size/rank works O((N+M) α(N)). Use long long for inconvenience.

    Implementation details:

    • Input edges: maybe store in vector<pair<int,int>> edges(M+1) (1-indexed) or 0-index with offset.
    • DSU arrays: parent[N+1], size[N+1].
    • Initialize parent[i]=i, size[i]=1.
    • cur = (ll)N*(N-1)/2.
    • ans vector of length M+1.
    • ans[M] = cur.
    • For i from M down to 1: int u = edges[i].first, v = edges[i].second; int ru = find(u), rv = find(v); if (ru != rv) { cur -= (ll)size[ru] * size[rv]; // union by size if (size[ru] < size[rv]) swap(ru, rv); parent[rv] = ru; size[ru] += size[rv]; } ans[i-1] = cur;
    • Output ans[1] through ans[M] each on new line.

    Edge Cases:

    • The graph is initially fully connected; that's guaranteed. It doesn't matter if we trust that? The problem says: "Initially, we can travel between any two islands using some of these bridges." So yes.
    • The reverse process assumes that initially the graph with no edges is disconnected and inconvenience = total pairs. That is correct.
    • Some edges might be redundant; union will handle that.

    Complexities: O(M α(N) + N). Memory O(N+M).

    Now consider the input format: first line N M, then M lines of A_i B_i.

    Potential pitfalls: Use 64-bit integer for multiplication and cur. N up to 1e5, N*(N-1)/2 = ~5e9 fits in 64-bit. Actually 1e5*99999/2 = 4,999,950,000 ~5e9 fits in 64-bit (max 9e18). So safe. But still we use long long.

    Now answer outputs as per examples.

    Let's implement.

    I'll use C++.

    We need fast I/O maybe.

    Implementation:

    #include <bits/stdc++.h> using namespace std; typedef long long ll;

    vector parent, sz;

    int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }

    void unite(int x, int y) { // we'll handle outside }

    int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; vector<pair<int,int>> edges(M+1); for (int i=1; i<=M; ++i) { cin >> edges[i].first >> edges[i].second; } parent.resize(N+1); sz.resize(N+1, 1); for (int i=1; i<=N; ++i) parent[i]=i; vector ans(M+1); ll cur = (ll)N * (N-1) / 2; ans[M] = cur; for (int i=M; i>=1; --i) { int u = edges[i].first, v = edges[i].second; int ru = find(u), rv = find(v); if (ru != rv) { cur -= (ll)sz[ru] * sz[rv]; if (sz[ru] < sz[rv]) swap(ru, rv); parent[rv] = ru; sz[ru] += sz[rv]; } ans[i-1] = cur; } for (int i=1; i<=M; ++i) { cout << ans[i] << '\n'; } return 0; }

    Check for off-by-one: ans indices: ans[M] is after all M removals; then ans[M-1] after M-1 removals? Actually we computed ans[i-1] after adding edge i (i from M to 1). That's state after removal i-1. So ans[0] after 0 removals (initial). So ans[1] after 1 removal, ans[2] after 2 removals, ... ans[M] after M removals. So output from 1 to M correct.

    Edge cases: M=0? But constraints M>=1. N>=2.

    Now the problem statement: "Initially, we can travel between any two islands using some of these bridges." So initial graph is connected. But our reverse process doesn't rely on that; it just builds from empty.

    Thus solution complete.

    Let's test with given examples:

    Example1: Output: 0 0 4 5 6 matches.

    Example2: 8 9 12 14 15 matches.

    Example3: N=2 M=1 edge 1-2. Initially total pairs=1. ans[1]=1. Process i=1: add edge1, find(u)!=find(v), sizes1,1 => cur=1-1=0. ans[0]=0. Output ans[1]=1. Matches.

    All good.

    Thus answer is to reverse order and use DSU.

    Now produce final answer. ```cpp

    #include <bits/stdc++.h> using namespace std; using ll = long long;

    vector parent, sz;

    int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }

    int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; vector<pair<int, int>> edges(M + 1); for (int i = 1; i <= M; ++i) { cin >> edges[i].first >> edges[i].second; }

    parent.resize(N + 1);
    sz.resize(N + 1, 1);
    for (int i = 1; i <= N; ++i) parent[i] = i;
    
    vector<ll> ans(M + 1);
    ll cur = (ll)N * (N - 1) / 2;
    ans[M] = cur;  // after all M bridges have collapsed
    
    for (int i = M; i >= 1; --i) {
        int u = edges[i].first, v = edges[i].second;
        int ru = find(u), rv = find(v);
        if (ru != rv) {
            cur -= (ll)sz[ru] * sz[rv];
            // union by size
            if (sz[ru] < sz[rv]) swap(ru, rv);
            parent[rv] = ru;
            sz[ru] += sz[rv];
        }
        ans[i - 1] = cur;  // state after collapse i-1
    }
    
    for (int i = 1; i <= M; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
    

    }