Java O(M*N) Solution
Find out all friendships that already possible w/o any teaching\n- the rest we try to teach using 1 language, find out from all language, what is the minimum we
- Find out all friendships that already possible w/o any teaching\n- the rest we try to teach using 1 language, find out from all language, what is the minimum we need to teach\n```\nclass Solution {\n    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {\n        Map<Integer, Set<Integer>> languagesMap = new HashMap<>();\n        for(int i = 0; i < languages.length; i++) {\n            languagesMap.put(i + 1, new HashSet<>());\n            for(int l : languages[i]) {\n                languagesMap.get(i + 1).add(l);\n            }\n        }\n        boolean[] alreadyCan = new boolean[friendships.length];\n        for(int j = 1; j <= n; j++) {\n            for(int i = 0; i < friendships.length; i++) {\n                if(languagesMap.get(friendships[i][0]).contains(j) && languagesMap.get(friendships[i][1]).contains(j)) {\n                    alreadyCan[i] = true;\n                }\n            }            \n        }\n        int minTeach = Integer.MAX_VALUE;\n        for(int i = 1; i <= n; i++) {\n            Set<Integer> teachSet = new HashSet<>();\n            for(int j = 0; j < friendships.length; j++) {\n                if(alreadyCan[j]) continue;\n                if(!languagesMap.get(friendships[j][0]).contains(i)) teachSet.add(friendships[j][0]);\n                if(!languagesMap.get(friendships[j][1]).contains(i)) teachSet.add(friendships[j][1]);\n            }\n            minTeach = Math.min(teachSet.size(), minTeach);\n        }\n        return minTeach;\n    }\n}\n```
[]