Depth-First Search Traversal

You are given a directed graph and a starting node. Your task is to perform a Depth-First Search (DFS) traversal on the graph and print the nodes in the order they are first visited.

The DFS must follow the order of adjacent nodes as given in the input. When processing a node, push its adjacent nodes onto a stack in reverse order of their appearance in the input. This ensures the DFS order is as expected.

Note: Only nodes that are reachable from the start node should be printed.

For example, consider the graph:

6
6
A B
A C
B D
B E
C F
E F
A

The DFS traversal starting from node A would produce:

A B D E F C

Implement the DFS function accordingly.

inputFormat

The input is given on standard input and has the following format:

1. The first line contains an integer n, the number of nodes in the graph.
2. The second line contains an integer m, the number of edges in the graph.
3. The next m lines each contain two strings u and v representing a directed edge from node u to node v.
4. The last line contains a string, the starting node for the DFS traversal.

It is guaranteed that node labels do not contain spaces.

outputFormat

Output the nodes in the order they are visited by the DFS traversal, separated by single spaces, on a single line to standard output.

For example:

A B D E F C

## sample

6
6
A B
A C
B D
B E
C F
E F
A

A B D E F C