All Paths in a Directed Graph

You are given a directed graph with ( n ) nodes represented by an adjacency matrix. Each entry ( m[i][j] ) is ( 1 ) if there is a directed edge from node ( i ) to node ( j ), and ( 0 ) otherwise. Given two nodes ( a ) (the start) and ( b ) (the destination), find all possible paths from ( a ) to ( b ) without revisiting any node.

The input is read from standard input and the output should be printed to standard output. Each valid path is printed on a separate line with nodes separated by a single space. The paths should be printed in lexicographical order (when compared as sequences of numbers). If there is no valid path, output nothing.

inputFormat

The first line contains three integers: ( n ), ( a ), and ( b ), where ( n ) is the number of nodes, ( a ) is the starting node, and ( b ) is the destination node.

This is followed by ( n ) lines, each containing ( n ) integers. The ( j^{th} ) integer in the ( i^{th} ) line represents ( m[i][j] ), which is ( 1 ) if there is a directed edge from node ( i ) to node ( j ) and ( 0 ) otherwise.

outputFormat

Print each valid path from node ( a ) to node ( b ) on a new line. Each path is represented as a sequence of node indices separated by a single space. The paths must be printed in lexicographical order. If no path exists, do not print anything.## sample

4 0 3
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0

0 1 2 3