Odd Puzzle Reachability

The Odd Puzzle is a generalization of the classic 8-puzzle game. In this game, you are given an n × n grid (where n is an odd number) containing exactly one blank space and the numbers 1 through n^2 - 1 without repetition. A move consists of swapping the blank space with one of its adjacent (up, down, left, right) numbers.

For example, a 3 × 3 grid (which is the standard 8-puzzle) might look like:

5 2 8
1 3 _
4 6 7

In this configuration, the blank (denoted by _) can be swapped with the number above it, to its left, or below it (if available).

In the Odd Puzzle game, you are given two configurations of the n × n grid. Your task is to determine whether it is possible to transform the first configuration into the second configuration by a sequence of valid moves.

Key Observation: For odd-sized grids, the reachability is determined solely by the parity of the inversion count. Let \( inv(A) \) be the number of inversions in configuration A (ignoring the blank). Two configurations are reachable from each other if and only if:

[ inv(\text{initial}) \equiv inv(\text{target}) \pmod{2} ]

inputFormat

The first line contains an odd integer n (n ≥ 3), representing the size of the grid.

The next n lines describe the first configuration. Each line contains n tokens separated by spaces. Each token is either an integer or an underscore (_) representing the blank.

The following n lines describe the second configuration in the same format.

outputFormat

Output a single line with YES if the first configuration can be transformed into the second configuration by a sequence of moves, or NO otherwise.

sample

3
5 2 8
1 3 _
4 6 7
5 2 8
1 3 7
4 6 _

YES