BOJ 6913 Constrained Permutations

문제 링크:

문제 내용

1부터 $n$까지의 정수가 정확히 한 번씩 포함되는 수열 중에서, $k$개의 다음 형태의 조건을 모두 충족하는 것의 개수를 구하세요.

• i j: $i$보다 $j$가 뒤에 등장합니다.

입력

첫 번째 줄에 $n$이 주어집니다. ($1 \le n \le 9$)

두 번째 줄에 $k$가 주어집니다. ($0 \le k \le 15$)

다음 줄부터 $k$줄에 걸쳐서, 한 줄에 하나의 조건이 주어집니다. 조건은 두 개의 수 $i$와 $j$의 순서로 주어집니다. ($1 \le i, j \le n$, $i \neq j$)

출력

문제의 정답을 출력합니다.

문제 풀이