题目描述

Alice 和 Bob 很喜欢玩一种需要频繁洗牌的牌类游戏。由于他们经常玩，两人的洗牌动作不仅很快，而且每次都完全一致：Alice 每次洗牌都会按照同一个置换重新排列牌组，Bob 也同样如此。

他们从一副按顺序排列的牌开始，随后轮流洗牌：

1. Alice 先洗一次；
2. Bob 再洗一次；
3. Alice 再洗一次；
4. 如此交替进行。

他们知道，经过若干次洗牌后，牌组一定会重新恢复为最初的顺序，但不知道最少需要多少次洗牌。

请计算使牌组第一次恢复原顺序所需的最少洗牌次数。

由于 Alice 和 Bob 在有限时间内最多只能完成 $10^{12}$ 次洗牌，如果答案严格大于 $10^{12}$，则应输出字符串 huge。

输入格式

第一行包含一个整数 $n$：

表示牌的数量。

第二行包含 $n$ 个两两不同的整数 $a_1,a_2,\ldots,a_n$。其中 $a_i$ 表示 Alice 洗牌后，原本位于位置 $i$ 的牌会移动到位置 $a_i$。

第三行包含 $n$ 个两两不同的整数 $b_1,b_2,\ldots,b_n$。其中 $b_i$ 表示 Bob 洗牌后，原本位于位置 $i$ 的牌会移动到位置 $b_i$。

两个序列均为 $1$ 到 $n$ 的排列。

输出格式

输出一个正整数 $m$，表示牌组第一次恢复原顺序所需的最少洗牌次数。

如果该次数严格大于 $10^{12}$，输出：

huge

样例 1

输入

3
2 3 1
3 1 2

输出

2

样例 2

输入

6
5 1 6 3 2 4
4 6 5 1 3 2

输出

5

样例 3

输入

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

输出

10