import java.util.*;

class GraphAllTopSorts {
    int V;  // No. of vertices
    LinkedList<Integer>[] adj;  //Adjacency List
    boolean[] marked;   //Boolean array to store the visited nodes
    List<Integer> list; //
    int[] indegree; //integer array to store the indegree of nodes
    Stack<Integer> st;
    LinkedList<Integer> q;

    //Constructor
    public GraphAllTopSorts(int v) {
        this.V=v;
        this.adj = new LinkedList[v];
        for (int i=0;i<v;i++) {
            adj[i] = new LinkedList<Integer>();
        }
        this.indegree = new int[v];
        this.marked = new boolean[v];
        list = new ArrayList<Integer>();
        this.st = new Stack<Integer>();
        this.q = new LinkedList<Integer>();
    }

    // function to add an edge to graph
    public void addEdge(int v, int w){
        adj[v].add(w);
        // increasing inner degree of w by 1
        indegree[w]++;
    }

    public void getKosarajuTopologicalSort(int val) {
        for (int i=0;i<V;i++) {
            if (!marked[i]) {
                dfs(i);
            }
        }

        if (val==0) {
            while (!q.isEmpty()) {
                System.out.print(q.remove() + " ");
            }
            System.out.print("\n");
        }
        else {
            while (!st.isEmpty()) {
                int w = st.pop();
                System.out.print(w + " ");
            }
            System.out.print("\n");
        }

    }

    public void dfs(int v) {
        marked[v] = true;
        Iterator<Integer> iter = adj[v].listIterator();
        while (iter.hasNext()) {
            int w = iter.next();
            if (!marked[w]) {
                dfs(w);
            }
        }
        q.add(v);
        st.push(v);
    }

    public GraphAllTopSorts reverse() {
        GraphAllTopSorts g2 = new GraphAllTopSorts(V);
        for (int i=0;i<V;i++) {
            Iterator<Integer> iter = adj[i].listIterator();
            while (iter.hasNext()) {
                int w = iter.next();
                g2.addEdge(w, i);
            }
        }
        return g2;
    }

    // Driver program to test above functions
    public static void main(String[] args) {
        // Create a graph given in the above diagram
        GraphAllTopSorts g = new GraphAllTopSorts(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        System.out.println("PostOrder for original graph");
        g.getKosarajuTopologicalSort(0);

        System.out.println("Kosaraju Topological Sort (Reverse PostOrder) for reverse graph");
        GraphAllTopSorts g2 = g.reverse();
        g2.getKosarajuTopologicalSort(1);


    }
}