This problem requires the following skills. They are all important for your improvement in competitive programming, so we recommend beginners practice them, referring to the sample code.

• Two-dimensional arrays
• If statements
• Nested for loop

First, prepare an array \(\text{adj}_{i, j}\) to store the information whether there is an edge between Vertices \(i\) and \(j\). This can be constructed in an \(O(N^2 + M)\) time.

Next, iterate through all combinations of \((a, b, c)\). There are \(\frac{N(N - 1)(N - 2)}{6}\) such pairs, which you can inspect exhaustively in the execution time limit, because \(N \leq 100\). Use \(\text{adj}_{i, j}\) to check if there is an edge between \(a\) and \(b\), \(b\) and \(c\), and \(c\) and \(a\), and add \(1\) to the answer if the conditions are satisfied.

The overall time complexity is \(O(N^3)\).

Sample code (C++)

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

int main() {
    int n, m;
    cin >> n >> m;
    vector adj(n, vector<bool>(n));
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u -= 1, v -= 1;
        adj[u][v] = adj[v][u] = true;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (adj[i][j] and adj[j][k] and adj[k][i]) {
                    ans += 1;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

Sample code (Python)

n, m = map(int, input().split())

adj = [[False] * n for _ in range(n)]

for _ in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  adj[u][v] = True
  adj[v][u] = True

ans = 0

for i in range(n):
  for j in range(i + 1, n):
    for k in range(j + 1, n):
      if adj[i][j] and adj[j][k] and adj[k][i]:
        ans += 1

print(ans)