1
class Solution {
2
  public int minNumberOfSemesters(int n, int[][] relations, int k) {
3
    int[] ok = new int[1 << n];
4
    int[] dp = new int[1 << n];
5
    Arrays.fill(dp, 30);
6
    dp[0] = 0;
7
    for (int[] r : relations) {
8
      ok[r[1] - 1] |= 1 << (r[0] - 1);
9
    }
10
    for (int i = 0; i < 1 << n; i++) {
11
      if (dp[i] != 30) {
12
        tryAll(0, k, i, i, n, ok, dp);
13
      }
14
    }
15
    return dp[(1 << n) - 1];
16
  }
17

18
  private void tryAll(int idx, int k, int cur, int old, int n, int[] ok, int[] dp) {
19
    for (int i = idx; i < n && k > 0; i++) {
20
      if ((old & (1 << i)) == 0 && (old & ok[i]) == ok[i]) {
21
        tryAll(i + 1, k - 1, cur | 1 << i, old, n, ok, dp);
22
      }
23
    }
24
    dp[cur] = Math.min(dp[cur], dp[old] + 1);
25
  }
26
}