1017. Print All Paths Between Two Nodes

Given a directed acyclic graph with n nodes and a list of directed edges, return all simple paths from src to dst. Each path is the list of nodes visited in order; return the list of all paths sorted in ascending (lexicographic) order. If there is no path, return an empty list. The input is JSON {n, edges, src, dst}.

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

Output: Nested array — all paths, sorted.

Examples

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

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

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

Constraints

• 1<=n<=15
• directed acyclic

Asked by