Problem G
Gigagame

It is 10 years from now and “thosantreem”, famous for a reason, has achieved rank 1 in all known competitive multiplayer games on Earth, such as League of Legends, TFT, Valorant, and many more. Eventually, he starts to get bored and thinks that playing against other people is simply too easy. So he decides to play against himself — that’s right — this time, he challenges himself to conquer all known singleplayer games.

His first victim is “Gigagame” (created by “gigachao”), a ripoff version of the well-known “Color Sort Puzzle” mobile ad game. After a first glance, thosantreem already knows that this game is too easy. So he decides to cosplay Ayanokoji and make you solve this game for him instead.

Of course, you are annoyed at him. So you decide to construct an impossible-to-solve instance of the game and give it to him. However, before you can do that, you must first understand the rules and determine which instances of the game are solvable and which are not.

The rules of the game are as follows:

You are given an integer $n$ representing the number of colors. There are exactly $2n$ pieces in total, and each color appears on exactly two pieces.

There are $n+1$ stacks. Initially, exactly one stack is empty, and each of the remaining $n$ stacks contains exactly two pieces. Within each stack, the pieces are arranged in some order from top to bottom.

In one move, you may remove the top piece from any non-empty stack and place it on top of another stack. However, the following conditions must always be satisfied:

• If the destination stack is not empty, then the color of the moving piece must match the color of the piece currently on top of that stack.

• No stack may ever contain more than two pieces.

You win the game if you can rearrange the pieces so that, for every color, the two pieces of that color end up on the same stack. Since there are $n$ colors and $n+1$ stacks, exactly one stack will remain empty in the final configuration.

Given the initial configuration of the stacks, determine whether it is possible to win the game.

Input

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of colors.

The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le n$), where $a_i$ is the color of the top piece of the $i$-th non-empty stack.

The third line contains $n$ integers $b_1, b_2, \dots , b_n$ ($1 \le b_i \le n$), where $b_i$ is the color of the bottom piece of the $i$-th non-empty stack.

It is guaranteed that for every color $c$ ($1 \le c \le n$), the value $c$ appears exactly twice.

Output

Print YES if it is possible to win the game. Otherwise, print NO.

Sample 1 Explanation

Initially, the $n=3$ non-empty stacks (written as (top, bottom)) are:

and there is one extra empty stack.

One possible winning sequence of moves is:

• Move the top piece of the second stack (color $2$) onto the empty stack.

  Now the stacks are:

  \[ (1,3),\ (3),\ (2,1),\ (2) \]

• Move the top piece of the third stack (color $2$) onto the stack whose top is also color $2$.

  Now:

  \[ (1,3),\ (3),\ (1),\ (2,2) \]

• Move the top piece of the first stack (color $1$) onto the stack whose top is color $1$.

  Now:

  \[ (3),\ (3),\ (1,1),\ (2,2) \]

• Move the single piece of color $3$ onto the other stack whose top is color $3$.

  Now:

  \[ (3,3),\ \emptyset ,\ (1,1),\ (2,2) \]

All colors have been grouped into their own stacks, and exactly one stack is empty, so the game is winnable. Hence the output is YES.

Note that in the first move, we cannot place the color $2$ piece directly onto the other stack with top color $2$, because that would violate the rule that no stack may contain more than two pieces.

3
1 2 2
3 3 1

YES

7
1 2 3 4 5 6 7
2 3 4 5 6 7 1

YES