护照是旅行者进入外国时在世界范围内使用的一种证件。
在一颗星球上有
你有一个喜欢旅行的朋友。他梦想环游世界,但他最开始没有护照。因此,他计划通过重复如下两个操作来环游所有的
- 他获得了他目前所在国家签发的护照
- 他移动到一个可以使用他目前拥有的护照入境的国家
当你听说了他的计划时,你想知道他是否可以实现他的计划,并且如果可以的话,他至少需要获得多少本护照。因为你不知道他住在哪儿,你假设他住在
给定护照和他可能居住的国家,写一个程序计算对于所有可能,他是否能够环游所有
输入格式
第一行一个整数
接下来
接下来一行一个整数
接下来
输出格式
输出
样例输入 1
4 1 3 2 4 2 3 4 4 1 1
样例输出 1
2
假设你的朋友住在国家
- 他获得国家
签发的护照。 - 使用国家
签发的护照,他移动到国家 。 - 他获得国家
签发的护照。 - 使用国家
签发的护照,他移动到国家 。 - 使用国家
签发的护照,他移动到国家 。
因为如果他获得小于等于
这组样例满足所有子任务的限制。
样例输入 2
5 1 5 2 4 2 3 3 5 1 5 1 3
样例输出 2
4
假设你的朋友住在国家
- 他获得国家
签发的护照。 - 使用国家
签发的护照,他移动到国家 。 - 他获得国家
签发的护照。 - 使用国家
签发的护照,他移动到国家 。 - 他获得国家
签发的护照。 - 使用国家
签发的护照,他移动到国家 。 - 他获得国家
签发的护照。 - 使用国家
签发的护照,他移动到国家 。
因为如果他获得小于等于
这组样例满足子任务
样例输入 3
5 1 1 2 3 1 5 3 4 5 5 5 1 2 3 4 5
样例输出 3
-1 2 1 2 -1
例如,如果你的朋友住在国家
另一方面,如果你的朋友住在国家
这组样例满足子任务
样例输入 4
4 1 2 1 2 3 4 3 4 4 1 2 3 4
样例输出 4
-1 -1 -1 -1
这组样例满足子任务
数据范围
对于所有输入数据,满足:
详细子任务附加限制及分值如下表所示。
子任务编号 | 附加限制 | 分值 |
---|---|---|
无附加限制 |
时间限制:2s
空间限制:1024MB