题目描述

给定一个 $2\times n$ 的整数矩阵 $a$ 和正整数 $m$，满足 $1\leq \lvert a_{i,j}\rvert \leq m$。

有一个值域为 $[1,m]$ 的排列 $p$，令大小为 $2\times n$ 的正整数矩阵 $b$ 为：

$b_{i,j} = \begin{cases} a_{i,j}&a_{i,j}>0\\p_{-a_{i,j}}&a_{i,j}<0\end{cases}.$

定义矩阵 $b$ 的四连通块为，选择矩阵 $b$ 的若干元素，使得这些元素是四连通的，并且所有元素的值相等。

你需要选择一个值域为 $[1,m]$ 的排列 $p$，求出矩阵 $b$ 的极大四连通块数的最小值。

输入格式

第一行为一个正整数 $n$，代表矩阵大小。

接下来两行每行 $n$ 个整数，表示矩阵 $a$。

输出格式

输出一行一个正整数表示矩阵 $b$ 的极大四连通块数的最小值。

样例输入 1

5 3
1 2 1 2 1
-1 -2 -3 -3 -3

样例输出 1

5

样例输入 2

15 3
1 -1 1 -1 -1 -2 2 -1 3 3 3 -3 -2 -2 1
2 -1 1 1 -1 -2 -1 2 -2 3 3 -2 -2 -2 3

样例输出 3

9

样例解释

对于第一个样例：

选择 $p=[3,2,1]$，矩阵 $b$ 为：

1 2 1 2 1
3 2 1 1 1

其总共有 $5$ 个极大四连通块，标记如下：

A B C D C
E B C C C

可以证明矩阵 $b$ 的极大四连通块数的最小值为 $5$。

数据范围

对于所有数据，

• $1\leq n\leq 10^5$，
• $1\leq m\leq 300$，
• $\forall 1\leq i\leq 2,1\leq j\leq n$，$1\leq\lvert a_{i,j}\rvert\leq m$。

• 特殊性质 A：$\forall1\leq i\leq n$，$a_{1,i}=a_{2,i}$。

2s / 1024MB