Topological Sorting of a Directed Acyclic Graph

You are given a directed graph defined by a set of nodes and edges. Your task is to perform a topological sort on the graph. In other words, if the graph is a Directed Acyclic Graph (DAG), output the nodes in an order such that for every directed edge (u \to v), node (u) comes before (v) in the ordering. If the graph contains a cycle, output the exact message: Graph has at least one cycle.

The input is provided via standard input. The first line contains two integers (n) and (m) denoting the number of nodes and the number of edges, respectively. The second line contains (n) space-separated strings representing the labels of the nodes. Each of the next (m) lines contains two strings (u) and (v) representing a directed edge from (u) to (v>.

inputFormat

Standard input (stdin) follows this format:

n m node_1 node_2 ... node_n u1 v1 u2 v2 ... um vm

where (n) is the number of nodes, (m) is the number of edges, and each edge is given by two node labels.

outputFormat

If the graph is a DAG, output a single line containing the nodes in a valid topological order separated by a single space. If the graph contains a cycle, output exactly:

Graph has at least one cycle## sample

4 4
A B C D
A B
A C
B D
C D

A B C D