List Directories Lexicographically

You are given a directory structure represented as a tree along with a set of parent-child relationships. Your task is to output the names of all directories by performing a depth-first search (DFS) starting from the root directory. When traversing, you must visit the child directories in lexicographical order. Formally, if two sibling directories have names a and b, then a should be visited before b if \(a < b\) in lexicographical order.

The DFS order should be printed as a single line of directory names separated by spaces.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer \(N\), representing the total number of directories.
• The second line contains a string denoting the name of the root directory.
• The third line contains an integer \(M\), the number of parent-child relationships.
• Each of the next \(M\) lines contains two strings \(P\) and \(C\), indicating that directory \(C\) is a child of directory \(P\).

It is guaranteed that all directory names are unique and that the tree is well-formed.

outputFormat

Print a single line containing the directory names in the order they are visited by the DFS, with each name separated by a single space.## sample

7
root
6
root a
root b
a d
a c
b f
b e

root a c d b e f