题目描述

请注意，在 LibreOJ 上，本题暂时只支持 C++ 语言提交。

题目译自 JOISC 2016 Day3 T1 「ダンジョン 2」

你知道 Just Ordinary Inventions 公司吗？这个公司就是专搞一些「仅仅是平凡的发明」的。

JOI 君正在玩 Just Ordinary Inventions 公司最新开发的游戏。

这款游戏要求玩家探索由一些房间和道路组成的地牢。一条道路双向连接地牢中的两个不同房间。对于任意两个不同的房间，最多只有一条道路连接它们，并且不存在两端连接相同房间的道路。同时我们已知你可以通过一些道路，从任意一个房间到达任意另一个房间。房间彼此之间很相似，如果对于两个房间，与它们各自连接的道路数量相同的话，仅通过观察两个房间的状态是无法区分出这两个房间的。

在游戏中，每个房间都有标记和台座，以帮助玩家攻略这个地牢。离开这个房间的道路可以被标记标为道路 $1$，道路 $2$，……，以此类推。地牢的结构在游戏中不会改变。因此，如果你从相同的房间出发，走相同编号的路，到达的房间也是相同的。房间中的台座上有一个宝石。宝石的颜色是颜色 $1$，颜色 $2$，……，颜色 $X$ 中的一种，游戏开始时，所有房间中宝石的颜色都是颜色 $1$。除非玩家控制，否则宝石的颜色不会改变。

JOI 君发现，如果知道了地牢的构造，也就是说，地牢里的房间是如何被道路相连的，那么这个游戏可以轻易地被攻略。然而，JOI 君在尝试了很多方法之后仍然无法确定地牢的构造。因此你决定替代 JOI 君，写一个程序确定这个地牢的构造。

问题

探索地牢，并写一个程序确定地牢的构造。然而，JOI 君并不想完全知道这个地牢的构造，所以程序也不需要直接回答这个地牢的构造。对于从 $1$ 到 $R$（包括两端）的每个整数 $i$，你需要回答「有多少对房间之间最少通过 $i$ 条道路可以互相到达」（对于两个房间 $a,b$，数对 $(a,b)$ 和数对 $(b,a)$ 是一样的，本题中我们考虑无序数对）。

在探索地牢时，可以进行如下操作：

• 询问当前的房间与多少道路相连。
• 查询当前房间台座上宝石的颜色。
• 让台座上的宝石变成你所指定的颜色（你也可以指定为当前宝石的颜色），之后，选择一条道路并去往与这条道路相连的另一个房间。
• 查询你所走过的最后一条路，在当前房间下是第几条路。

实现细节

你需要写一个程序实现对 JOI 君的解答过程。这个程序需要引入 dungeon2.h 库。

这个程序必须实现如下函数：

• $\texttt{void Inspect(int R)}$

  这个函数只会在开始时调用一次。

  • 参数 $R$ 表示对于从 $1$ 到 $R$（包括两端）的每个整数 $i$，你需要回答「有多少对房间之间最少通过 $i$ 条道路可以互相到达」（对于两个房间 $a,b$，数对 $(a,b)$ 和数对 $(b,a)$ 是一样的，本题中我们考虑无序数对）。

你可以调用如下函数做出回答：

• $\texttt{void Answer(int D, int A)}$

  • 参数 $\texttt{D, A}$ 表示「有 $A$ 对房间之间最少通过 $D$ 条道路可以互相到达」。

  调用 $\texttt{Answer}$ 函数时，需要满足如下条件：

  • $\texttt D$ 是 $1$ 到 $R$ 之间的整数（包括两端）。如果不满足，则会被判为 Wrong answer [1]。
  • 对于相同的参数 $\texttt D$，函数不能调用超过一次。如果不满足，则会被判为 Wrong answer [2]。
  • $\texttt{Answer}$ 函数必须调用恰好 $R$ 次。如果不满足，则会被判为 Wrong answer [3]。
  • $\texttt A$ 必须是最少通过 $\texttt D$ 条道路可以互相到达的房间对数。 如果不满足，则会被判为 Wrong answer [4]。

  如果 $\texttt{Answer}$ 函数调用错误，之后的程序便不会再执行了。

除此之外，程序中还可以调用如下函数：

• $\texttt{void Move(int I, int C)}$

  • 参数 $\texttt I$ 是玩家选择用来移动的道路编号。在这次调用之后，玩家立刻使用这条道路从当前房间前往与这条道路相连的另一个房间。
  • 参数 $\texttt C$ 表示在离开房间之前，将台座上的宝石变为颜色 $C$。

  调用 $\texttt{Move}$ 函数时，需要满足以下条件：

  • 参数 $\texttt I$ 必须是一个大于等于 $1$ 且小于等于 $K$ 的整数，这里 $K$ 指与玩家当前所在房间相连的道路条数。 如果不满足，则会被判为 Wrong answer [5]。
  • 参数 $\texttt C$ 必须是一个大于等于 $1$ 且小于等于 $X$ 的整数，这里 $X$ 指宝石颜色的种类数。对于每个子任务，$X$ 的值是确定的。如果不满足，则会被判为 Wrong answer [6]。
  • $\texttt{Move}$ 函数至多被调用 $1\ 500\ 000$ 次。如果不满足，则会被判为 Wrong answer [7]。

• $\texttt{int NumberOfRoads()}$

  • 这个函数返回与玩家当前所处房间相连的道路条数。

• $\texttt{int LastRoad()}$

  • 这个函数返回玩家所走过的最后一条道路，对于玩家当前所处房间来说是第几条路。然而，如果这个函数在第一次调用 $\texttt{Move}$ 函数前被调用，则返回 $-1$。

• $\texttt{int Color()}$

  • 这个函数返回玩家当前所处的房间中宝石的颜色。

在调用函数 $\texttt{Inspect}$ 后，判定答案是否正确。

你的程序可以实现任何其他函数，或定义全局变量。但你的程序无论如何都不可以与标准输入输出或其他文件交互。

如何编译运行

附加文件中包含一个样例交互器和交互库，仅用作测试。

样例交互器包含一个文件，文件名为 grader.c 或 grader.cpp。为了测试程序，需执行如下命令：

• C 语言

gcc -std=c11 -O2 -o grader grader.c Memory2.c -lm

• C++ 语言

g++ -std=c++11 -O2 -o grader grader.cpp Memory2.cpp

如果编译成功，则会生成一个名为 grader 的可执行文件。

请注意，实际判题过程和样例的判题过程不同。样例判题程序作为单进程执行。这个程序需要从标准输入中读入，并输出到标准输出中。

样例交互程序输入

第一行包含三个整数 $N,X,R$，用一个空格隔开。分别表示房间有 $N$ 个，分别从 $1$ 到 $N$ 编号，宝石颜色有 $X$ 种，程序需要回答从 $1$ 到 $R$ 的答案。

接下来 $2N$ 行，第 $2i-1\ (1\le i\le N)$ 行有一个整数 $D_i$，表示与房间 $i$ 相连的道路条数。第 $2i\ (1\le i\le N)$ 行有 $D_i$ 个整数 $T_{i,1},T_{i,2},\ldots,T_{i,D_i}$，表示通过与房间 $i$ 相连的第 $j\ (1\le j\le D_i)$ 条道路可以移动到房间 $T_{i,j}$。

接下来 $R$ 行，第 $j\ (1\le j\le R)$ 行一个整数 $A_j$。表示有 $A_j$ 对房间之间最少通过 $j$ 条道路可以互相到达。换句话说，对于每个整数 $j\ (1\le j\le R)$，如果调用 $\texttt{Answer}$ 时的参数有 $\texttt D$ 是 $j$，$\texttt A$ 是 $A_j$，那么交互程序就会判定答案正确，否则将判定为答案错误。

样例交互程序中，玩家起始时所处房间为房间 $1$。

样例交互程序输出

如果样例交互程序正常退出，它会向标准输出输出一行如下内容：

• 如果答案正确，输出 $\texttt{Move}$ 函数调用的次数，如 Accepted : #move = 8。
• 如果不正确，输出错误的类型，如 Wrong answer [1]。

数据范围

对于所有输入数据，满足以下条件。对于 $N,D_i$ 和 $T_{i,j}$ 的意义，请参考「样例交互程序输入」。

• $2\le N\le 200$
• $3\le X\le 100$
• $1\le R\le 200$
• $1\le D_i\le N-1\ (1\le i\le N)$
• $1\le T_{i,j}\le N$ 且 $T_{i,j}\neq i\ (1\le i\le N,1\le j\le D_i)$
• $T_{i,1},T_{i,2},\ldots,T_{i,D_i}$ 之间互不相同
• 对于任意 $i,j\ (1\le i\le N,1\le j\le D_i)$，都存在 $k\ (1\le k\le D_{T_{i,j}})$ 满足 $T_{T_{i,j},k}=i$
• 你可以通过一些道路从任意一个房间到达任意另一个房间。

详细子任务附加限制及分值如下表。输入中地牢中房间数为 $N$，道路数为 $M$。

子任务	附加限制	分值
$1$	$N\le 50,M\le 100,X=100$	$17$
$2$	$N\le 50,M\le 100,X=3$	$27$
$3$	$X=3$	$56$

对于子任务 $3$，得分按如下标准确定。

• 令 $L$ 为对于此子任务下所有测试点下列值的最大值
  • $\texttt{Move}$ 调用次数 $C$ 和 $M$ 的比值，也就是 $\dfrac{C}{M}$。
• 此时，这个子任务的得分为：
  • 若 $L\le 14$，则得 $56$ 分。
  • 若 $14<L\le 32$，则得 $\lfloor 70-L\rfloor$ 分。
  • 若 $32<L\le 64$，则得 $\left\lfloor 54-\dfrac{L}{2}\right\rfloor$ 分。
  • 若 $64<L$，则得 $0$ 分。

这里，$\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。

请注意，如果程序正确退出，并且答案被判为正确，在详细结果列中将显示 Accepted。但当子任务 $3$ 出现 $64<L$ 的情况时，详细结果会显示答案错误。

样例交互过程

输入为

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

样例交互过程如下

函数调用	返回值
$\texttt{Inspect(3)}$
$\texttt{NumberOfRoads()}$	$1$
$\texttt{LastRoad()}$	$-1$
$\texttt{Move(1, 2)}$
$\texttt{Color()}$	$1$
$\texttt{LastRoad()}$	$1$
$\texttt{NumberOfRoads()}$	$3$
$\texttt{Move(1, 3)}$
$\texttt{Color()}$	$2$
$\texttt{Answer(1, 4)}$
$\texttt{Answer(2, 2)}$
$\texttt{Answer(3, 0)}$