Cards Flipping

Interview

Time limit1sMemory limit2048 MB

Summary

Each card has a color on each side and can be flipped. Find the maximum number of distinct colors that can appear on the top sides.

Level: Medium6 of 10
Topics: Union-find, Graph
Solved: No attempts yet

Problem

The magician $B$ has $n$ cards in a row on a desk. Each card has two sides, and each side has one color. The top side of a card is the side facing up, and the bottom side is the side facing down. Flipping a card swaps its top and bottom sides. We want to find the maximum number of distinct colors that can appear on the top sides.

In the example below, there are 5 cards in a row. From left to right, the top sides are violet, red, violet, violet, and red. The bottom sides are red, violet, blue, yellow, and red.

If the 3rd and 4th cards from the left are flipped, the top sides change as shown below.

The top sides then show 4 distinct colors, which is the maximum for this case.

Input

The first line contains an integer $n$ ( $1 \le n \le 200\,000$ ), the number of cards. The cards are numbered from 1 to $n$ . The second line contains the colors on the top sides of cards 1 through $n$ . The third line contains the colors on the bottom sides of cards 1 through $n$ . Each color is a nonnegative integer not exceeding $10^6$ .

Output

Print one line containing the maximum number of distinct colors on the top sides.

Examples3

Example 1
Input
```
5
0 1 0 0 1
1 0 2 3 1
```
Expected output
```
4
```
Example 2
Input
```
2
3 5
5 1
```
Expected output
```
2
```
Example 3
Input
```
3
0 1 0
1 0 2
```
Expected output
```
3
```