文档介绍：: .
（招聘面试）IOI中国国家
个宝箱，让她自己去找。CC 姐姐手边仅
有的称量工具就是壹架天平，每次能够比较俩只宝箱的重量。她不仅想找到那只
次重的宝箱，而且想用尽量少的称量次数找到它，因为小 K 告诉她，如果她的策
略能保证于最坏情况下称量次数最少的话，她仍会得到意外的惊喜！
【输入文件】
第壹行是壹个整数 n，表示宝箱的个数。
第二行是壹个整数 m，表示事先公布的宝箱间的轻重关系数目。
接下来的 m 行，每行俩个整数 x 和 y（1≤x,y≤n）表示事先公布了宝箱 x 要
重于宝箱 y。
【约定】
2≤ n≤200000
2≤ m≤200000
事先公布的关系没有自相矛盾
【交互方法】本题是壹道交互式题目，你的程序只能够访问输入文件 以及和测试
库进行交互。
输入文件格式如前所述。
测试库提供了若干函数，它们的用法和作用如下：
init 必须先调用，但只能调用壹次，用作初始化测试库。
compare(x,y)的 作 用 是 比 较 第 x 只 宝 箱 和 第 y 只 宝 箱 的 重 量 ，
1≤x,y≤n。若第 x 只宝箱比第 y 只宝箱重，返回 1，否则返回-1。
answer(x)的作用是向测试库方案结果，x 表示次重的宝箱的编号。当这
个函数被调用后，测试库会自动中止你的程序。
【对使用 Pascal 选手的提示】
你的程序应当使用如下的语句引用测试库。
usesgift_lib_p;
测试库使用的函数原型为：
procedureinit;
functioncompare(x,y:longint):longint;
procedureanswer(x:longint);
【对使用 C/C++选手的提示】
你应当建立壹个工程，把文件 包含进来，然后于程序头加壹行：
#include“”
测试库使用的函数原型为：
voidinit();
intcompare(int,int);
voidanswer(int);
【你如何测试自己的程序】
除了按照上述格式建立 之外，请另外建立壹个名为“”的
文件。该文件包含 n 个互不相同整数，绝对值不超过 2*10 9，依次表示每只宝箱的重量。
执行你的程序，此时测试库会产生输出文件 ，该文件中包括了你程
序和库交互的记录和最后的结果。
如果程序正常结束， 的最后壹行包含壹个整数，为你查询的次数。
如果程序非法退出，我们不保证 中的内容有意义。
正式测试时，测试库会自行生成宝箱的重量，且使得每次回答尽量对你不利。
【样例】
内容如下
3
1
2 内容如下
壹种可能得满分的调用方案如下：
Pascal 选手的调用方法 C/C++选手的调用方法 说明
init; init(); 初始化程序
compare(3,1); compare(3,1); 返回 1
compare(2,1); compare(2,1); 返回-1
answer(1); answer(1); 1 确实是次重的宝箱，共称量 2 次
注意，该例子只是对库函数的使用说明，且没有算法上的意义。
【评分方法】
如果你的程序有下列情况之壹，该测试点 0 分：
自行终止；
非法调用库