You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [ui, vi] indicates that there is an undirected edge between ui and vi.

A connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

&nbsp;
Example 1:

Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.


Example 2:

Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
Output: 0
Explanation: There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.


&nbsp;
Constraints:


	2 &lt;= n &lt;= 400
	edges[i].length == 2
	1 &lt;= edges.length &lt;= n * (n-1) / 2
	1 &lt;= ui, vi &lt;= n
	ui != vi
	There are no repeated edges.


class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        result = n ** 2 # placeholder value
        adj = [set() for _ in range(n + 1)]
        visited = set()
        for edge in edges:
            adj[edge[0]].add(edge[1])
            adj[edge[1]].add(edge[0])
        for first in range(1, n + 1): # iterate through every node
            for second in adj[first]: # iterate through every neighbor of the first node
                e1 = tuple(sorted((first, second)))
                if e1 in visited:
                    continue
                visited.add(e1) # mark e1 (first -> second) as visited because we don't want to visit (second -> first) again
                for third in adj[second]:
                    if third == first: # skip if the third node is the first node (we need the first node to be its neighbor rather than itself!)
                        continue
                    e2 = tuple(sorted((first, third)))
                    if first in adj[third]: # we don't check if e2 is in visited because the third node is not the current node being explored
                        visited.add(e2) # we need to mark e2 as visited because one end of e2 is the first node and if we have checked (third -> first), we don't need to check (first -> third) again
                        degree = len(adj[first]) - 2 + len(adj[second]) - 2 + len(adj[third]) - 2
                        result = min(result, degree)
        return -1 if result == n ** 2 else result
class Solution {
public int minTrioDegree(int n, int[][] edges) {
	// to store edge information
    boolean[][] graph = new boolean[n+1][n+1];
	//to store inDegrees to a node(NOTE: here inDegree and outDegree are same because it is Undirected graph)
    int[] inDegree = new int[n+1];
    
    for(int[] edge : edges) {
        graph[edge[0]][edge[1]] = true;
        graph[edge[1]][edge[0]] = true;
        
        inDegree[edge[0]]++;
        inDegree[edge[1]]++;
    }
    
    int result = Integer.MAX_VALUE;
    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n; j++) {
            if(graph[i][j]) {
                for(int k=j+1; k<=n; k++) {
                    if(graph[i][k] && graph[j][k]) {
                        result = Math.min(result, inDegree[i] + inDegree[j] + inDegree[k] - 6);
                    }
                }
            }
        }
    }
    
    
    return result == Integer.MAX_VALUE ? -1 : result;
}
}
class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<unordered_set<int>> adj(n+1);
        int res = INT_MAX;
        for (vector<int>& edge : edges) {
            adj[edge[0]].insert(edge[1]);
            adj[edge[1]].insert(edge[0]);
        }

        for (int i = 1; i < n; ++i) {
            for (auto iter1 = adj[i].begin(); iter1 != adj[i].end(); ++iter1) {
                if (*iter1 <= i) continue;
                for (auto iter2 = adj[i].begin(); iter2 != adj[i].end(); ++iter2) {
                    int u = *iter1, v = *iter2;
                    if (v <= u) continue;
                    if (adj[u].count(v)) {
                        int cur = adj[i].size() + adj[u].size() + adj[v].size() - 6;
                        res = min(res, cur);
                    }
                }
            }
        }

        return res == INT_MAX ? -1 : res;
    }
};
var minTrioDegree = function(n, edges) {
    // create an adjacency list of all the edges;
    const adjacencyList = new Array(n + 1).fill(0).map(() => new Set());
    for (const [x, y] of edges) {
        adjacencyList[x].add(y);
        adjacencyList[y].add(x);
    }

    let minimumDegree = Infinity;

    // Find all the combinations of 3 vertices that connect
    // and if they connect calculate the degree
    for (let i = 1; i <= n; i++) {
        for (let j = i + 1; j <= n; j++) {
            for (let k = j + 1; k <= n; k++) {
                if (adjacencyList[i].has(j) && adjacencyList[i].has(k) && adjacencyList[j].has(k)) {
                    // We minus 6 because we have 3 vertices and each vertices has 2 edges
                    // going out to the 3 connecting nodes
                    const degree = adjacencyList[i].size + adjacencyList[j].size + adjacencyList[k].size - 6;
                    minimumDegree =
                        Math.min(minimumDegree, degree);
                }
            }
        }
    }

    return minimumDegree === Infinity ? -1 : minimumDegree;
};
Minimum Degree of a Connected Trio in a Graph