gistfile1.txt

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // Initialize familiarity matrix, true means they are familiar
    vector<vector<bool>> familiar(n + 1, vector<bool>(n + 1, true));

    // Mark the pairs who are not familiar with each other
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        familiar[x][y] = false;
        familiar[y][x] = false;
    }

    // To handle segments efficiently, use a 2D prefix sum array
    vector<vector<int>> prefix_sum(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] + (!familiar[i][j] ? 1 : 0);
        }
    }

    int efficient_count = 0;

    // Check all possible segments [a, b]
    for (int a = 1; a <= n; ++a) {
        for (int b = a; b <= n; ++b) {
            bool is_efficient = true;
            for (int i = a; i <= b && is_efficient; ++i) {
                for (int j = i + 1; j <= b && is_efficient; ++j) {
                    if (!familiar[i][j]) {
                        is_efficient = false;
                    }
                }
            }
            if (is_efficient) {
                ++efficient_count;
            }
        }
    }

    cout << efficient_count << endl;

    return 0;
}