An assembly of n parts (labeled 0..n-1) has precedence constraints given as directed edges (u v means part u must be assembled before part v). Count how many distinct full orderings of all parts respect every constraint.
Input format
Line 1: two integers n and m — the number of nodes (labeled 0 through n-1) and the number of directed edges.
Each of the next m lines: two integers , a directed edge from to (read as: must come before ).
It is guaranteed the graph is acyclic, with no self-loops and no duplicate edges.
Output format
A single integer: the number of valid orderings.
Constraints
- 1 <= n <= 12
- 0 <= m <= n*(n-1)/2
- 0 <= u, v <= n-1; the graph is a DAG
- The answer fits in a 64-bit signed integer.