1109. Count Hamiltonian Paths in DAG (Bitmask DP)

Given a directed acyclic graph with n nodes and edges, count the number of Hamiltonian paths — directed paths that visit every node exactly once following the edges. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the number of Hamiltonian paths.

Examples

Input: {"n":3,"edges":[[0,1],[1,2],[0,2]]}
Output: 1
Explanation: Only 0->1->2 covers all nodes.

Input: {"n":3,"edges":[[0,1],[0,2]]}
Output: 0
Explanation: No single path covers all.

Input: {"n":1,"edges":[]}
Output: 1
Explanation: The single node is a path.

Constraints

• 1<=n<=16
• directed acyclic

Asked by