A DAG on n nodes represents a critical-path network, where an edge u v means u precedes v. Among all directed paths, some achieve the maximum number of nodes (the longest chains). Count how many distinct directed paths attain that maximum node count. Two paths are distinct if their node sequences differ. When there are no edges, every single node is a longest path (of one node).
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 directed paths having the maximum number of nodes.
Constraints
- 1 <= n <= 40
- 0 <= m <= 400
- 0 <= u, v <= n-1; the graph is a DAG
- The answer fits in a 64-bit signed integer.