ACM中的M题

题号：NC276079
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\textbf{}$ 此题为 $B$ 题的困难版本，与 $B$ 题有是否排序、交换元素限制以及数据范围的不同

有一个长度为 $n$ 的数组 $\{a_i\}$ ，每个 $\{a_i\}$ 属于且仅属于一个类别 $\{b_i\}$

已知 $\{a_i\}$ 无相同元素

你可以多次交换同一个类别下任意2个元素
直到每个位置的元素和原来都不相同
若有解请输出最小交换次数，反之无解输出 -1

第一行输入一个正整数 
第二行输入  个非负整数 
第三行输入  个非负整数  ，表示   类别

数据保证无相同

一个整数表示结果
若有解，输出最小交换次数
反之，输出 -1

示例1

复制

3
1 2 3
1 1 1

复制

显然3个元素属于统一类别
第一次交换第一第二位置变为 [2,1,3]
第二次交换第一第三位置变为 [3,1,2]
显然无更少的交换次数能满足条件

示例2

复制

3
0 1 2
0 1 2

复制

-1

显然3个数类别均不相同不可交换

示例3

复制

4
0 1 2 3
0 2 2 0

复制

示例4

复制

2
1 2
0 0

复制