This article addresses the problem of identifying and counting specific 4-tuples based on a given set of 3-tuples. Given a collection of M three-element tuples (a, b, c), the objective is to determine the total number of distinct 4-element tuples (x, y, z, w) that satisfy the following conditions:

1. (x, y, z) is one of the input 3-tuples.
2. The 3-tuples (x, y, w), (x, z, w), and (y, z, w) must all be present in the original input collection.

It's important to note that the order of elements within a 3-tuple matters (e.g., (1,2,3) is distinct from (1,3,2)), and w must be distinct from x, y, and z if (x,y,z,w) is to be a 4-tuple, although the problem statement implicitly handles w != z in the iteration logic, and w would naturally be distinct from x and y by checking for the existence of (x,y,w) etc.

Initial Approach: Brute Force Enumeration

A straightforward, albeit inefficient, method involves iterating through each provided 3-tuple (x, y, z) from the input. For each such tuple, we then iterate through all possible candidate values for w (from 1 to N, where N is the maximum possible value for an element). For each w, we check if the three required support tuples—(x, y, w), (x, z, w), and (y, z, w)—exist in the input set.

To check for the existence of a 3-tuple, a naive scan of all M input tuples would take O(M) time. With M initial tuples, an O(N) loop for w, and O(M) for each existence check, the total time complexity becomes approximately O(M * N * M * 3), which simplifies to O(N * M^2). Given typical constraints (e.g., N = 2000, M = 50000), this approach is computationally prohibitive.

First Optimization: Efficient Triplet Existence Checks

The primary bottleneck in the brute-force method is the O(M) lookup time for checking if a specific 3-tuple exists. This can be significantly optimized using hash tables. By storing all input 3-tuples in a suitable hash-based data structure, we can achieve an average O(1) lookup time for existence.

A nested std::unordered_map structure is ideal for representing sparse 3-dimensional data. For instance, std::unordered_map<int, std::unordered_map<int, bool>> triplet_presence[N_MAX + 1]; can effectively model the presence of (a,b,c). triplet_presence[a][b][c] would be true if (a,b,c) exists. This reduces the time complexity of each existence check from O(M) to O(1) (on average).

With this optimization, the overall complexity becomes O(M * N). While better, O(50000 * 2000) is still 10^8, which might be too slow for typical time limits.

Second Optimization: Reducing Candidate w Search Space

The O(N) loop for candidate w values is still a concern. However, observe that the tuple (x, y, w) must be one of the input triplets. This means w is not arbitrary; it must be a value that has appeared as the third element alongside x and y in some input tuple (x, y, k).

We can pre-process the input tuples to build a list of all potential w values for any given (x,y) pair. A data structure like std::unordered_map<int, std::vector<int>> third_element_candidates[N_MAX + 1]; can store this. For each input tuple (a, b, c), we would add c to third_element_candidates[a][b].

Then, instead of iterating w from 1 to N, we only iterate through the values stored in third_element_candidates[x][y]. This significantly reduces the number of w candidates, especially if (x,y) pairs are not associated with many distinct third elements. In the best case, if each (x,y) pair has a bounded number of associated z values, the total complexity approaches O(M).

Applying both optimizations results in a highly efficient algorithm in terms of time complexity.

Advanced Optimization: Mitigating unordered_map Memory Overhead

Even with optimal time complexity, competitive programming problems often have strict memory limits. A common pitfall with std::unordered_map (and similar hash tables) is its behavior when querying for non-existent keys using operator[]. If map[key] is accessed and key does not exist, std::unordered_map will insert a default-constructed element for key, consuming memory.

In our scenario, during the final check if (triplet_presence[x][z][w] && triplet_presence[y][z][w]), it's possible that (x,z,w) or (y,z,w) might not be actual input triplets. If they aren't, the operator[] calls would create new, unnecessary entries in triplet_presence, potenntially leading to a Memory Limit Exceeded (MLE) error under extreme sparse data conditions.

To counter this, we introduce an additional pre-check. We maintain a boolean adjacency matrix bool pair_co_occurrence[N_MAX + 1][N_MAX + 1]; This matrix stores whether any two distinct nodes u and v have ever appeared together in any input 3-tuple (e.g., (u, v, k), (u, k, v), or (k, u, v)). When processing an input (a, b, c), we set pair_co_occurrence[a][b] = true, pair_co_occurrence[a][c] = true, and pair_co_occurrence[b][c] = true.

Before performing the costly unordered_map lookups for triplet_presence[x][z][w] and triplet_presence[y][z][w], we first check simpler conditions: if (pair_co_occurrence[x][w] && pair_co_occurrence[z][w] && pair_co_occurrence[y][w]). If any of these pair_co_occurrence checks fail, we know that the corresponding 3-tuple (e.g., (x,z,w)) cannot exist, and thus there's no need to access triplet_presence. This prevents unordered_map from creating spurious entries for non-existent keys, significantly reducing memory consumption. This N*N boolean array itself uses O(N^2) memory, which is acceptable for N=2000 (approximately 4MB).

Optimized C++ Implementation

The following code incorporates all the described optimizations:

#include <iostream>
#include <vector>
#include <unordered_map>

// Maximum value for an element (N)
const int MAX_NODE_VAL = 2005;
// Maximum number of input triplets (M)
const int MAX_TRIPLETS = 50005;

// Structure to hold an input triplet for easier iteration
struct InputTriplet {
    int val1, val2, val3;
};

// Global variables for problem parameters and result
int num_nodes, num_input_triplets;
long long solution_count = 0; // Use long long for answer to prevent overflow

// Stores presence of (val1, val2, val3) -> triplet_presence_map[val1][val2][val3] = true
// Using an array of unordered_maps for better performance with N_MAX
std::unordered_map<int, std::unordered_map<int, bool>> triplet_presence_map[MAX_NODE_VAL];

// Stores for a given (val1, val2) all observed val3 values
// w_candidates_for_pair[val1][val2] = vector of possible val3s
std::unordered_map<int, std::vector<int>> w_candidates_for_pair[MAX_NODE_VAL];

// Boolean matrix to check if two nodes have ever appeared together in any triplet
// Prevents unnecessary unordered_map insertions
bool nodes_co_occur[MAX_NODE_VAL][MAX_NODE_VAL];

// Stores all input triplets for convenient iteration
std::vector<InputTriplet> initial_triplets;

int main() {
    // Optimize C++ standard streams for competitive programming
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_nodes >> num_input_triplets;

    initial_triplets.reserve(num_input_triplets); // Pre-allocate memory

    // Process all input triplets
    for (int i = 0; i < num_input_triplets; ++i) {
        int u, v, k;
        std::cin >> u >> v >> k;

        initial_triplets.push_back({u, v, k});

        // Mark this triplet as present
        triplet_presence_map[u][v][k] = true;

        // Store candidate w values for (u,v)
        w_candidates_for_pair[u][v].push_back(k);

        // Mark co-occurrence for pairs
        nodes_co_occur[u][v] = true;
        nodes_co_occur[u][k] = true;
        nodes_co_occur[v][k] = true;
    }

    // Iterate through each input triplet (x, y, z)
    for (const auto& current_triplet : initial_triplets) {
        int x = current_triplet.val1;
        int y = current_triplet.val2;
        int z = current_triplet.val3;

        // Iterate through potential 'w' values. These are values 'k' such that (x,y,k) exists.
        // The list is stored in w_candidates_for_pair[x][y].
        // The .count() method is used to avoid creating default entries in the map if x or y are not keys
        if (w_candidates_for_pair[x].count(y)) {
            for (int w : w_candidates_for_pair[x][y]) {
                // 'w' cannot be the same as 'z' for a distinct 4-tuple
                if (w == z) {
                    continue;
                }

                // Pre-check using the co-occurrence matrix to prevent unnecessary unordered_map accesses
                // If any required pair (x,w), (z,w), or (y,w) has never co-occurred, the triplet cannot exist.
                if (nodes_co_occur[x][w] && nodes_co_occur[z][w] && nodes_co_occur[y][w]) {
                    // Final check for the existence of the other two required triplets
                    // Using .count() for map lookups to avoid accidental insertion if key is not present
                    if (triplet_presence_map[x].count(z) && triplet_presence_map[x][z].count(w) &&
                        triplet_presence_map[y].count(z) && triplet_presence_map[y][z].count(w)) {
                        
                        solution_count++;
                    }
                }
            }
        }
    }

    std::cout << solution_count << std::endl;

    return 0;
}