Flight Route Completion

You are given a list of flight routes between cities and a starting city. Each flight route is represented by a pair of city names (source and destination). Your task is to determine whether it is possible to start at the given city, visit every city exactly once, and return to the starting city. In other words, you must decide if there exists a Hamiltonian cycle in the directed graph defined by the flight routes.

Formally, let \( G = (V, E) \) be a directed graph where \( V \) is the set of all cities and \( E \) is the set of flight routes. You need to check if there exists a sequence of cities \( [v_1, v_2, \dots, v_k] \) such that:

[ v_1 = v_k = \text{startCity}, \quad {v_1, v_2, \dots, v_{k-1}} = V, \quad \text{and} \quad \forall i, (v_i, v_{i+1}) \in E. ]

If such a route exists, output Yes; otherwise, output No.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer \( n \), the number of flight routes.
• Each of the next \( n \) lines contains two space-separated strings representing the source city and the destination city.
• The last line contains a string representing the starting city.

It is guaranteed that all city names consist of uppercase or lowercase English letters and are non-empty.

outputFormat

Output a single line to standard output (stdout) containing either Yes if it is possible to form such a route, or No otherwise.

4
A B
B C
C D
D A
A

Yes