1204. Count Paths in DAG with Constraints

Given a directed acyclic graph with n nodes (0 to n-1) and directed edges, count the number of distinct directed paths from node 0 to node n-1. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the number of distinct paths.

Examples

Input: {"n":4,"edges":[[0,1],[0,2],[1,3],[2,3]]}
Output: 2
Explanation: 0->1->3 and 0->2->3.

Input: {"n":2,"edges":[[0,1]]}
Output: 1
Explanation: One direct path.

Input: {"n":3,"edges":[[0,1],[1,2],[0,2]]}
Output: 2
Explanation: Two paths to node 2.

Constraints

• 2<=n<=10^4

Asked by