hardGraphsPure DSA~30 min

List Every Path From Source to Sink in a DAG

A directed acyclic workflow graph runs from stage 0 to the final stage n-1. Enumerate every distinct path from start to finish.

Problem

Given a directed acyclic graph of n nodes as graph where graph[i] lists the out-neighbors of node i, return all paths from node 0 to node n-1. Each path is the sequence of node indices visited.

Input

An adjacency list graph of out-edges for a DAG.

Output

A list of all source-to-sink paths.

Constraints

2 <= n <= 15
graph is a DAG; node n-1 may be a sink.
The number of paths can be exponential in n.

Examples

Example 1

Input

graph = [[1,2],[3],[3],[]]

Output

[[0,1,3],[0,2,3]]

Two distinct paths reach node 3.

Example 2

Input

graph = [[4,3,1],[3,2,4],[3],[4],[]]

Output

[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

All five source-to-sink paths are listed.