1025. Count Paths from Source to Destination in DAG

Given a directed acyclic graph with n nodes and a list of directed edges, return the number of distinct paths from src to dst. The input is JSON {n, edges, src, dst}.

Input: JSON {n, edges, src, dst}.

Output: Integer — the number of distinct paths.

Examples

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

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

Input: {"n":2,"edges":[],"src":0,"dst":1}
Output: 0
Explanation: No path.

Constraints

• 1<=n<=10^4
• directed acyclic

Asked by