Project Completion

In this problem, you are given a set of projects and a list of dependencies between these projects. A dependency [a, b] means that project a must be completed before project b can begin. Your task is to determine whether it is possible to complete all the projects.

The problem can be modeled using a directed graph. Let (n) be the number of projects and let (m) be the number of dependencies. For each dependency (a \to b), it adds a directed edge from node (a) to node (b). The projects can all be completed if and only if the graph contains no cycles (i.e. it is a Directed Acyclic Graph, DAG).

inputFormat

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

n -- the number of projects
p1 p2 ... pn -- a space-separated list of project identifiers (each identifier is a string without spaces)
m -- the number of dependencies
Then follow m lines, each containing two space-separated project identifiers a b meaning that project a must be completed before project b.

outputFormat

Print a single line to standard output (stdout):

True if all projects can be completed (i.e., there is no cycle in the dependency graph), or
False otherwise.## sample

1
p1
0

True