Expert.
Put your skills to the test.

Problem summary

Process players in increasing label order. On player a’s day play all remaining games incident to a; all its larger remaining neighbors must also have a game between each pair. Count the total number of distinct games eventually played.

Constraints

1 ≤ N,M ≤ 100000; 1 ≤ x<y ≤ N; no duplicate initial games.

Worked example

Official statement example.

9 8
2 5
2 6
2 7
1 2
1 3
4 8
4 7
7 8

15

Solution analysis

1. Let S[u] contain u’s current larger neighbors. Eliminating u would normally add a clique on S[u], which may have quadratic size. Instead represent that pending clique compactly through its smallest vertex p: at p’s future elimination the rest of S[u] will again become a clique.
2. At u’s turn count |S[u]| games. Remove its smallest member p and merge the remaining set into S[p]. This schedules all edges from p to the other clique members; the clique among those members is deferred to their own earliest future elimination. Ordered sets remove duplicate edges automatically.
3. Merge smaller sets into larger ones by swapping their containers first. In the sample eliminating 1 propagates neighbor 3 to S[2]; eliminating 2 then counts four games and propagates 5,6,7 to S[3]. This produces the same total 15 without materializing every clique edge immediately.

Why it works

Maintain that every deferred clique is represented at its least remaining vertex, whose set contains all other members. Eliminating u plays exactly one game with each distinct member of S[u]. The only new requirement is a clique on those members. Moving the remaining members to their minimum p represents precisely its incident edges, and recursively defers precisely the remaining clique. Thus each real game is counted exactly on its smaller endpoint’s day, and no unnecessary game is introduced.

Watch out. Count games in 64 bits. Never explicitly enumerate all pairs of a large neighbor set. Swapping set containers does not change vertex identities.

An independently written complete program with standard headers.

// Key idea: Maintain that every deferred clique is represented at its least remaining vertex, whose
// set contains all other members. Eliminating u plays exactly one game with each distinct member of
// S[u].
#include<iostream>
#include<set>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<set<int>>neighbors(n+1);
    for(int i=0;i<m;++i){
        int x,y;
        cin>>x>>y;
        neighbors[x].insert(y);
    }
    long long answer=0;
    for(int u=1;u<=n;++u){
        answer+=static_cast<long long>(neighbors[u].size());
        if(neighbors[u].empty()){
            continue;
        }
        int p=*neighbors[u].begin();
        neighbors[u].erase(neighbors[u].begin());
        if(neighbors[u].size()>neighbors[p].size()){
            neighbors[u].swap(neighbors[p]);
        }
        neighbors[p].insert(neighbors[u].begin(),neighbors[u].end());
        neighbors[u].clear();
    }
    cout<<answer<<'\n';
}