题目描述

这是本次互测最水的一道题，希望大家珍惜机会。

2015 年的集训队的集训队互测就要开始了。大爷们的时间很宝贵，每个人都有自己的安排。比如说 A 大爷要参加省选享受虐人的快感；B 大爷刚好某天和他的某个妹子约好了要去 XXX；C 大爷到外太空旅游去了，要过几天才回来，诸如此类。（为了保护当事人隐私权，所有人物名称皆为化名）

问题是，集训队互测的时间表和每天的出题人已经排好了。因为某种诡异的原因，时间被安排在了周末——意味着已经无法修改互测的时间了。唯一的方法就是更改互测的顺序。不过这种事情难不倒集训队的大爷们，所以 QQ 群上经常看到这样的对话：「orz XXX 大爷」「orz，有什么事么？」「4 月 20 号我要去参加省选啊，我们换一下好不？」「我这边没问题，这就去换吧。」

本来事情就这样解决了，但是由于大爷们实在是太神了，所以互测时间总是换来换去的。虽然大爷们对此毫不在意，但大爷们过于频繁的交换信息引发了庞大的信息爆炸，其总量超越了当今互联网的物理容量的总和，最终瘫痪了整个信息社会，引发了全球人民的联名抗议。这下就有点麻烦了。只能要求大爷们尽可能快地协商好了。

这个问题也难不倒大爷们，通过大爷们的量子计算机对平行世界的观测，从未来带来了安排好的时间表，所以只需要尽可能快地交换了。

现在已知：

1. 开始安排的互测时间表，以及未来的互测时间表。
2. 任意两个大爷交换互测时间所需时间为 $1\text{ s}$，会带来 $2^{g_{i,j}}$ 的信息量。若 $g_{i,j}=-1$ 则表明这两位大爷的交流产生的信息量已经无法测定，即无穷大。
3. 一个大爷在一个时刻只可以进行一次交换，但是同一时刻可以发生许多交换。
4. 为了拯救被崩溃的人类社会，希望能够得到一种安排，使得大爷们交换所占用的时间尽可能小。在占用时间最小的前提下，请减小大爷们交换产生的总信息量。
5. 总信息量的计算公式为大爷每一次交换产生的所有信息量的乘积。

请 2014 年的您编程完成这个来自未来任务，拯救人类的未来吧！（若对题意有所疑惑，请仔细参考样例及样例说明）

输入格式

首先输入 $n$，表示 2015 年国家队候选人人数，大爷从 $1$ 开始标号。

接下来一行输入 $n$ 个数 $\{a_i\}$，表示开始安排的互测时间表：$a_i$ 表示第 $i$ 次测试是由 $a_i$ 这位大爷主持。

接下来一行输入 $n$ 个数 $\{b_i\}$，表示未来安排的互测时间表：$b_i$ 表示第 $i$ 次测试是由大爷 $b_i$ 主持。

接下来一个 $n\times n$ 的矩阵，第 $i$ 行第 $j$ 列表示 $g_{i,j}$。

输出格式

第一行输出一个整数，表示大爷交换的最小耗时，以秒为单位，具体见样例。

接下来输出一个整数，表示在最小耗时的前提下的最小信息量。

为了减少您写高精度的负担，若答案为 $\text{ans}$，请输出 $\text{ans}$ 以 $2$ 为底的对数，如果该信息量无法测定，请输出 $-1$。

9
1 2 3 4 5 6 7 8 9
2 3 1 5 6 4 8 7 9
1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2
1 2 3 3 3 3 3 3 3
1 2 3 4 4 4 4 4 4
1 2 3 4 5 5 5 5 5
1 2 3 4 5 6 6 6 6
1 2 3 4 5 6 7 7 7
1 2 3 4 5 6 7 8 8
1 2 3 4 5 6 7 8 9

2
17

1
1
1
-1

0
0

2
1 2
2 1
1 2
2 1

1
2

5
1 2 3 4 5
2 3 1 5 4
12 12 12 13 23
12 73 23 12 1
12 23 23 0 2
13 12 0 23 1
23 1 2 1 7

2
25

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

2
8

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

2
-1

样例解释

在样例 2 中，未来的顺序和现在的顺序没有区别，不需要交换，故时间和最小信息量都为 $0$。

在样例 3 中，我们只需要花费 $1\text{ s}$ 交换大爷 1 和大爷 2，信息量为 $2$，显然不存在其它方案。

在样例 4 中，置换 $(2,3,1,5,4)$ 可以分成两个轮换 $(1,2,3)(4,5)$，分别为长度为 $2$ 和长度为 $3$ 的轮换。显然最小所需时间为 $2$：第一秒交换 $(2,3)(4,5)$，第二秒交换 $(1,3)$。不过信息量最小的方案却为第一秒交换 $(1,2)(4,5)$，第二秒交换 $(3,1)$。

在样例 5 中，给定的是两个长度为 $4$ 的轮换。最小所需时间依旧为 $2$，因为我们既可以第一秒交换 $(1,4)(2,3)$，第二秒交换 $(2,4)$ 完成一个轮换，亦可以在第一秒交换 $(2,4)$ 第二秒交换 $(1,2)(3,4)$。无论哪种的最小信息量都为 $2\times 2\times 3=12$。但是如果我们第一秒交换 $(1,5)(2,8)(3,7)(4,6)$，第二秒交换 $(1,6)(2,5)(3,8)(4,7)$，所需要的最小信息量为 $8$。

在样例 6 中，给定的是一个长度为 $5$ 的轮换，最小所需时间依旧为 $2$，因为我们可以第一秒交换 $(2,5)(3,4)$，第二秒交换 $(1,2)(3,4)$ 完成轮换。显然第二问的答案为 $-1$。

数据范围与提示

对于 $100\%$ 的数据，$1\le n\le 100$，$\{a_i\},\{b_i\}$ 为排列。保证 $-1\le g_{i,j}\le 10^4$，保证 $g_{i,j}=g_{j,i}$，但是对于任意 $i$，$g_{i,i}$ 一定不为 $0$，意味着一旦大爷开始独自思考人生，世界将迎来末日。

给定一个置换，我们总是可以将其拆成轮换的形式。

考虑两个轮换 $A,B$，若存在 $A$ 中某元素与 $B$ 中某元素交换的代价不为 $-1$，在 $A,B$ 之间连一条边。

题目来源

2014 年国家集训队十五人互测