Các Thứ Tự Hợp Lệ · canuc80k1508

Có $N$ công việc được đánh số từ $1$ đến $N$ . Bạn cần sắp xếp tất cả công việc thành một thứ tự, mỗi công việc xuất hiện đúng một lần.

Có $M$ quan hệ dạng $x$ $y$ , yêu cầu công việc $x$ phải xuất hiện trước công việc $y$ . Các quan hệ được đảm bảo không tạo chu trình, vì vậy luôn tồn tại ít nhất một thứ tự hợp lệ.

Hãy đếm số thứ tự thỏa mãn toàn bộ các quan hệ.

Input

Dòng đầu chứa hai số nguyên $N$ và $M$ .
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ , biểu thị $x$ phải đứng trước $y$ .

Output

In một số nguyên - số thứ tự hợp lệ.

Constraints

$2 \leq N \leq 16$ .
$1 \leq M \leq N (N - 1) /2$ .
Trong mỗi quan hệ, $x \neq = y$ .
Không có hai quan hệ có hướng $(x, y)$ giống nhau.
Đồ thị quan hệ không có chu trình.

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 9$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Năm thứ tự hợp lệ là $1$ $2$ $3$ $4, 1$ $2$ $4$ $3, 2$ $1$ $3$ $4, 2$ $1$ $4$ $3$ và $2$ $4$ $1$ $3$ . Mỗi thứ tự đều đặt $1$ trước $3$ , đồng thời đặt $2$ trước cả $3$ và $4$ .

Ý tưởng: Với mỗi công việc v, lưu bitmask need[v] gồm các công việc bắt buộc đứng trước v. Đặt dp[mask] là số cách tạo một tiền tố chứa đúng các công việc trong mask.
Ý tưởng: Từ mask, thử chọn một công việc v chưa xuất hiện. Ta chỉ được đặt v tiếp theo khi mọi bit trong need[v] đã nằm trong mask, tức (need[v] & mask) == need[v]. Khi đó cộng dp[mask] vào dp[mask | (1 << v)].
Ý tưởng: Chứng minh đúng. dp[0] = 1 biểu diễn tiền tố rỗng duy nhất. Mỗi phép chuyển thêm đúng một công việc chưa dùng và chỉ thực hiện khi toàn bộ tiền đề của nó đã ở trong tiền tố, nên mọi tiền tố được đếm đều hợp lệ. Ngược lại, trong bất kỳ thứ tự hợp lệ nào, tại mỗi bước công việc tiếp theo đều có toàn bộ tiền đề ở trước nó, vì vậy chuỗi phép chuyển tương ứng tồn tại và là duy nhất. Do đó dp[(1 << N) - 1] đếm đúng mọi thứ tự hợp lệ, mỗi thứ tự đúng một lần.
Ý tưởng: Độ phức tạp. O(N·2^N) thời gian và O(2^N) bộ nhớ.