#16053. 「JOISC 2020 Day2」变色龙之恋

内存限制:512 MiB 时间限制:2000 ms 题目类型:交互
上传者: Woshiluo

题目描述

题目译自 JOISC 2020 Day2 T1「カメレオンの恋 / Chameleon’s Love

注意:在 LibreOJ 上,由于语言限制,目前只支持以下语言的提交:

  • C++ 11
  • C++ 17
  • C++ 11 (NOI)
  • C++ 11 (Clang)
  • C++ 17 (Clang)

在 JOI 动物园中,有着 2N 只变色龙,编号为 1\ldots 2N 。其中,有 N 只变色龙的性别为 X,其余 N 只的性别为 Y。

每只变色龙都有一个原色。关于原色的可公开情报如下:

  • 所有性别为 X 的变色龙的原色不同。
  • 对于每只性别为 X 的变色龙,都存在唯一的原色与其相同的变色龙,且性别为 Y。

现在,JOI 动物园迎来了恋爱的季节。每只变色龙都爱上了另一只变色龙。关于恋爱对象的可公开情报如下:

  • 每只变色龙都很专一于唯一一只异性的变色龙。
  • 一只变色龙和它的恋爱对象的原色不同。
  • 不存在两只变色龙同时追求另一只变色龙。

你可以召集一部分变色龙来组织一场会议。对于一只参加会议的变色龙 s ,令 t 为它的恋爱对象。 s 肤色由以下方式决定:

  • 如果 t 参加了这场会议,则 s 的肤色为 t 的原色。
  • 如果 t 没参加这场会议,则 s 的肤色为 s 的原色。

一只变色龙的肤色可以在不同的会议间发生改变。对于你组织的一场会议,你可以得到场上所有变色龙的肤色的种类数。

由于变色龙也会感到厌烦,所以你最多只能组织 20\,000 场会议。同时你需要根据你得到的信息,确定有哪些变色龙的原色相同。
请你写一个程序在组织不超过 20\,000 场会议的前提下确定所有相同原色的变色龙。

实现细节

你需要提交一个文件。
这个文件的名字应为 \texttt{chameleon.cpp}