class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> solution = new ArrayList<>();
        int[][] arr = new int[graph.length+1][graph.length+1];
        for(int i=0; i<graph.length; i++) {
            for(int j=0; j<graph[i].length; j++) {
                arr[i][graph[i][j]] = 1;
            }
        }
        Stack<List<Integer>> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        list.add(0);
        stack.add(list);
        while(!stack.isEmpty()) {
            list = stack.pop();
            int lastNode = list.get(list.size()-1);
            if(lastNode == graph.length - 1) {
                solution.add(list);
            } else {
                for(int i=0; i<graph.length; i++) {
                    if(arr[lastNode][i] != 0) {
                        List<Integer> thisList = new ArrayList<>();
                        thisList.addAll(list);
                        thisList.add(i);
                        stack.add(thisList);
                    }
                }
            }
        }       
        return solution;        
    }
}