Find All Paths in a Directed Graph

You are given a directed graph \(G=(V,E)\) with \(N\) vertices and \(M\) edges. Your task is to find all unique paths from a given start vertex \(s\) to a target vertex \(t\) using a Depth-First Search (DFS) approach. A path is a sequence of vertices such that there is a directed edge from each vertex to the next. Note that the graph might have cycles, so you must avoid revisiting vertices in the current path.

Input Format: The input is read from stdin and formatted as follows:

• The first line contains two integers \(N\) and \(M\), where \(N\) is the number of vertices and \(M\) is the number of directed edges.
• The next \(M\) lines each contain two strings \(U\) and \(V\) representing a directed edge from vertex \(U\) to vertex \(V\).
• The following line contains the start vertex \(s\>.
• The final line contains the target vertex \(t\>.

Output Format: For each unique path from \(s\) to \(t\), output a line with the vertices in the path separated by a single space. If no path exists, output nothing.

Use recursion to explore the graph. Be careful to avoid cycles by marking visited vertices along the current search path.

inputFormat

The input is provided via stdin in the following order:

N M
U1 V1
U2 V2
...
UM VM
s
t

Where:

• \(N\) is the number of vertices.
• \(M\) is the number of directed edges.
• Each of the next \(M\) lines contains two strings representing an edge from vertex \(U\) to vertex \(V\).
• \(s\) is the start vertex.
• \(t\) is the target vertex.

outputFormat

Print each unique path from \(s\) to \(t\) on a separate line, with vertices separated by a single space. If there are no paths, do not print anything.

## sample

4 3
A B
B C
C D
A
D

A B C D