Counting k-Cliques in a Social Network

You are given a social network of n users and m friendships. A friendship is represented as an undirected edge between two users. Your task is to count the number of distinct k-cliques in the network. A k-clique is a complete subgraph of k nodes such that there is an edge between every pair of nodes in the subgraph.

The relationship between nodes can be described using the adjacency matrix \(A\), where \(A_{ij} = 1\) if there is an edge between node \(i\) and node \(j\), and \(A_{ij} = 0\) otherwise. The task is to count all the possible subsets of nodes of size \(k\) which form a clique.

Note: Nodes are numbered from 1 to n.

inputFormat

The first line contains three integers: n, m, and k, representing the number of users, the number of friendships, and the desired clique size, respectively.

The next m lines each contain two integers u and v, indicating that there is a friendship between user u and user v.

outputFormat

Output a single integer, the total number of distinct k-cliques in the given network.

5 6 3
1 2
1 3
2 3
2 4
3 4
4 5

2