Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
2
Indexable
Never
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <bitset>
#include <cmath>
#include <ctime>
#define ff first
#define ss second
#define i1 fgvhdsjklfgh
#define j1 hvfdjsklfkgh
#define MAXN 500005
#define INF 1000000001LL
//#define int long long

using namespace std;

int n, m, v, u, to, i, j, cnt[MAXN];
vector <int> g[MAXN];
long long ans;
bool connected[MAXN];

bool cmp(int a, int b){
    if(g[a].size() != g[b].size())
        return g[a].size() < g[b].size();

    return a < b;
}

int main(){
    //freopen("input.txt", "r", stdin);
    ios_base :: sync_with_stdio(false);
    cin.tie();

    scanf("%d%d", &n, &m);

    for(i = 0; i < m; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        a--; b--;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(i = 0; i < n; i++)
        sort(g[i].begin(), g[i].end(), cmp);


    for(v = 0; v < n; v++){

        for(i = 0; i < g[v].size(); i++)
            connected[g[v][i]] = true;

        for(i = 0; i < g[v].size(); i++){
            u = g[v][i];

            for(j = g[u].size() - 1; j >= 0; j--){
                to = g[u][j];

                if(cmp(to, u))
                    break;

                if(connected[to])
                    cnt[to]++, cnt[u]++;
            }
        }

        for(i = 0; i < g[v].size(); i++){
            u = g[v][i];

            //cout << v << " " << u << " " << cnt[u] << endl;

            ans += cnt[u] * 1LL * (cnt[u] - 1) / 2;

            cnt[u] = 0; connected[u] = false;
        }
    }

    //cout << ans << endl;


    printf("%I64d", ans / 2);

    return 0;
}