Zoo Animal Rearrangement Puzzle

You are given a zoo with n enclosures, each occupied by an animal. The enclosures are connected by tunnels. Since all enclosures are full, you cannot simply move one animal into an empty enclosure. Instead, you are allowed to move several animals simultaneously according to the following rule:

• You may choose a set of enclosures and move the animal in each chosen enclosure to an adjacent enclosure via a tunnel. However, if an animal moves along a tunnel from enclosure A to enclosure B, then the animal in enclosure B must also move as a part of the same move.
• No tunnel (edge) may be used more than once in the same move.
• Important: A move which simply swaps animals between two connected enclosures (i.e. a 2-cycle) is not allowed because the animals would meet in the tunnel.

In effect, each legal move permutes the animals along one or more cycles. Every cycle involved in a move must have a length of at least \(3\) (i.e. \(k \ge 3\)).

You are given the current arrangement and your vision of the perfect arrangement for the animals. Determine whether it is possible to achieve the target configuration by performing a series of legal moves.

Note: The zoo is modeled as an undirected graph with n nodes (enclosures) and m edges (tunnels). The moves are restricted by the structure of this graph. In a connected component, if the graph is a tree (i.e. has no cycle) then the only move possible is trivial (i.e. no move) because any non-trivial move would require a 2-swap, which is not allowed.

inputFormat

The first line contains two integers \(n\) and \(m\) (1 \(\le\) \(n\) \(\le\) 10⁵, 0 \(\le\) \(m\) \(\le\) 10⁵): the number of enclosures and the number of tunnels.

The second line contains \(n\) strings, where the \(i\)th string represents the animal type in the \(i\)th enclosure in the initial configuration.

The third line contains \(n\) strings, where the \(i\)th string represents the animal type that should be in the \(i\)th enclosure in the target configuration.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) (1-indexed) indicating that there is a tunnel connecting enclosure \(u\) and enclosure \(v\). It is guaranteed that at most one tunnel exists between any two enclosures.

outputFormat

Output a single line containing YES if it is possible to achieve the target configuration using a sequence of valid moves, or NO otherwise.

sample

1 0
zebra
zebra

YES