Triangles

#include <bits/stdc++.h>

#define all(x) begin(x), end(x)

using namespace std;
using ll = long long;
const int N = 3003000;
vector<pair<int, int>> g[N];
vector<int> indG[N];

vector<pair<int, int>> edges;
int GlobalCnt[N];

void inc(int x, int y, int z) {
    // do something with triangles
    GlobalCnt[x]++;
    GlobalCnt[y]++;
    GlobalCnt[z]++;
}

int cmp2(pair<int,int> aa, pair<int,int> ba) {
    int a = aa.first;
    int b = ba.first;
    return g[a].size() < g[b].size() || (g[a].size() == g[b].size() && a < b);
}

int cmp(int a, int b) {
    return g[a].size() < g[b].size() || (g[a].size() == g[b].size() && a < b);
}


void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        int index = (int) edges.size();
        g[x].emplace_back(y, index);
        g[y].emplace_back(x, index);
        edges.emplace_back(x, y);
    }

    vector<tuple<int, int, int>> triples;
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), cmp);

    for (int v = 0; v < n; ++v)
        sort(g[v].begin(), g[v].end(), cmp2);
    vector<int> cnt(n, -1);
    vector<int> intCnt(n, -1);


    for (int v: p) {
        for (auto[w, wInd]: g[v]) {
            cnt[w] = v;
            intCnt[w] = wInd;
        }

        for (auto[u, uInd]: g[v]) {
            if (cmp(v, u))
                break;

            for (auto[w, wInd]: g[u]) {
                if (cmp(u, w))
                    break;
                if (cnt[w] >= 0) {
                    inc(wInd, uInd, intCnt[w]);
                }
            }
        }
        for (auto [w, wInd]: g[v]) {
            cnt[w] = -1;
        }
    }


    int pos = int(max_element(GlobalCnt, GlobalCnt + m) - GlobalCnt);
    cout << GlobalCnt[pos] << endl;
    auto[x, y] = edges[pos];
    cout << x + 1 << ' ' << y + 1 << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
}