d1p2 — CCO Canadian_Computing_Olympiad
Task type: batch | Time limit: 4 s | Memory limit: 1024 MB | Difficulty: 18
Algorithms: data structures, greedy, tree map, longest increasing sequence

# 2024 Canadian Computing Olympiad
# Day 1, Problem 2
# Pizza Party

**Time Limit:** 4 seconds

## Problem Description

Troy is fleshing out the details of his latest initiative, HackCCO! Everyone knows that the biggest appeal of any hackathon is the free food. As such, to ensure the unparalleled success of HackCCO, Troy ordered a comically large cart stacked with $N$ pizzas where the $i$-th pizza from the top of the cart has flavour $a_i$.

After the pizza cart arrives, Troy needs to arrange them into some number of stacks on a long table. To do this, he takes the pizzas one-by-one from the top of the cart and moves them onto the table, each time either placing the pizza on top of another stack of pizzas or forming a new stack on the table.

The $N$ hungry HackCCO participants are lined up to get pizza from the table, one-by-one. Troy knows that the $i$-th person in line has a favourite pizza flavour of $b_i$. When the $i$-th person walks up to the table, if they see any pizzas of their favourite flavour at the top of any stack they will take any one of them at random. Otherwise, they won't take anything and will leave the table hungry.

Of course, hungry coders are not happy coders, so Troy doesn't want anyone to leave the table hungry. Thus, he asks you to help him find an arrangement of pizzas on the table such that it is possible for nobody to leave hungry. Furthermore, out of all such arrangements, Troy wants you to find one that creates the smallest number of stacks on the table (after all, tables can only get so long). Help him find such an arrangement or determine that it's impossible!

## Input Specification

The first line of input contains a single integer $N$.

The second line of input contains $N$ space-separated integers $a_1, ..., a_N$ ($1 \le a_i \le N$).

The third line of input contains $N$ space-separated integers $b_1, ..., b_N$ ($1 \le b_i \le N$).

| Marks Awarded | Bounds on $N$      | Additional constraints |
| :------------ | :----------------- | :----------------------- |
| 3 marks       | $1 \le N \le 10^6$ | $1 \le a_i, b_i \le 2$  |
| 4 marks       | $1 \le N \le 5000$ | All $a_i$ are distinct  |
| 5 marks       | $1 \le N \le 10^6$ | All $a_i$ are distinct  |
| 6 marks       | $1 \le N \le 5000$ | None                     |
| 7 marks       | $1 \le N \le 10^6$ | None                     |

[Post-CCO edit: Subtasks 4 and 5 may not be solvable efficiently. CCO competitors were judged only on subtasks 1-3.]

## Output Specification

If it is impossible to arrange the pizzas as desired, output -1.

Otherwise, your output should consist of three lines. On the first line output $K$, the minimum number of stacks required. On the second line output $N$ space-separated integers $c_1, ..., c_N$ ($1 \le c_i \le K$), indicating that the $i$-th pizza should be placed on stack $c_i$. On the third line output $N$ space-separated integers $d_1, ..., d_N$ ($1 \le d_i \le K$), indicating that the $i$-th person in line takes their pizza from the $d_i$-th stack. This stack must have a pizza of flavour $b_i$ at the top when the $i$-th participant walks up to get their pizza.

## Sample Input 1

```
7
1 2 3 2 2 1 3
2 3 1 2 3 2 1
```

## Output for Sample Input 1

```
2
1 2 1 2 1 2 2
1 2 2 2 1 2 1
```

## Explanation of Output for Sample Input 1

<div align="center">
  <img src="_page_1_Figure_7.jpeg"  />
</div>

An illustration of the arrangement of pizzas on the table is shown above where red, yellow, and blue boxes represent pizzas of flavours 1, 2, and 3 respectively.

## Sample Input 2

```
2
1 2
1 1
```

## Output for Sample Input 2

```
-1

Starter code: