这是一道通信题。

题目描述

你是一名寻宝爱好者，这天，你听说在神秘的藏宝大学（Treasure Holding University）里藏有巨量的神秘宝藏，于是你打算前去一探究竟。

你在网上查到了一些关于藏宝大学的信息：学校里共有 $n$ 个标识点，$m$ 条双向道路连接这些标识点，使得任意两个标识点之间都可以通过道路互相到达。而所谓的神秘宝藏，就埋藏在某一个标识点下方。

你又联系到了一位藏宝大学的学长，据说他知道神秘宝藏的具体位置，但是他却不能直接告诉你——这算是泄露学校机密了。不过，你还是从他嘴里旁敲侧击到了一些有用的信息：

1、藏宝大学的道路是经过精心设计的，使得你从任意一个标识点出发，沿着任意的路径在学校里行走，最后回到原来的标识点，所经过的道路条数一定都是偶数。据说，这样可以有效缓解校园内的自行车拥堵问题。

2、学校所在的行政区域刚刚因为确诊病例升级为中风险，而学校规定14天内途径过中高风险地区的人员一律不得入校。因此，你只能乘坐直升机空降入校了。不过既然你都有直升机了，你也不打算沿着道路探索学校的每一个标识点，而是可以任选标识点降落，并在标识点之间任意跳跃。

3、在你进入校园之前，学长可以帮你在校园里留下一些提示信息——他会在学校里的每条道路上放置一个箭头，指向这条边连接的两个标识点中之一。但在你到达校园之后，就无法再联系上学长，只能靠你自己了。

4、学校的所有标识点是无标号的，这可能会增大你寻宝的难度。

不幸的是，你并没有拿到藏宝大学的地图，你甚至不知道道路条数 $m$ 的值，只知道标识点数 $n$ 的值。当然，学长肯定是知道全部信息的。

在引起校领导的注意之前，你只有有限的时间访问学校的若干个不同的标识点，并只能选择一个标识点进行宝藏挖掘。能否寻宝成功，就要看你和学长的配合了。

实现细节

你不需要，也不应该实现主函数，你只需要实现如下两个函数：

void Alice(const int testid, const int n, const int m, const int x, const int u[], const int v[], bool dir[]);

int Bob(const int testid, const int n);

Alice函数表示学长的提示。其中 $testid$ 为子任务编号， $n$ 为标识点数， $m$ 为道路数， $x$ 为宝藏所在的标识点的编号。数组 $u$ 和 $v$ 的大小均为 $m$ ，描述校园中的道路，第 $i$ 条道路连接标识点 $u[i]$ 和 $v[i]$ 。（所有编号和下标均从 $0$ 开始，下同。）

Alice函数需要将输出写入至 $dir$ 数组中，数组大小为 $m$ ，表示学长提示的每一条边的箭头指向。 $dir[i]=0$ 表示第 $i$ 条边的箭头指向 $v[i]$ ，反之则表示指向 $u[i]$ 。

Bob函数表示你的寻宝过程。其中 $testid$ 和 $n$ 的含义同上。该函数需要返回一个标识点编号，表示对该标识点进行宝藏挖掘。

Bob函数执行的过程中，可以调用如下函数：

vector<pair<int,bool>> discover(int pos);

该函数表示你访问编号为 $pos$ 的标识点，需要满足 $0 \leq pos \lt n$ 。通过访问你可以获取到与该点相连的所有边的信息，用一个 vector来存储。每条边的信息用一个 pair<int,bool>来表示，分别表示这条边指向的另一个点的编号以及这条边上的箭头方向（为 $0$ 表示指向另一个点，为 $1$ 表示指向自己）。另外，在同一个测试点中，你不能访问同一个标识点多于一次。

在一个测试点中，将会先执行一次 Alice函数，再执行一次 Bob函数。为了体现标识点的无标号性，执行完 Alice函数之后，所有标识点的编号将被随机打乱。Bob函数中涉及到的一切点的编号，包括调用 discover函数传入的 $pos$ 、调用 discover函数得到的出边指向的标识点编号、以及 Bob函数的返回值等，均指打乱后的编号。另外，discover函数返回的边的顺序也并非按照 Alice函数中传入的顺序，而是乱序给出的。（在部分测试点中，标识点的编号不会随机打乱，详见“数据范围”。）

另外，你也可以根据自己的需要，定义其他变量或者函数。但你定义的全局变量在 Alice函数中修改的值将不能应用于 Bob函数。

你的 Alice函数只能访问数组 $u、v$ 的 $0 \thicksim m-1$ 下标且不能对其进行修改，并只能访问和修改数组 $dir$ 的 $0 \thicksim m-1$ 位置， 越界访问可能出现意料不到的错误。

你的程序中，需要包含本题的头文件：

#include "treasure.h"

如何测试你的程序

本地已经下发了 $4$ 个文件：treasure.h、grader.cpp、Alice.cpp和 Bob.cpp。

你需要在本地将自己的程序命名为 treasure.cpp，其中包含你编写的 Alice和 Bob两个函数。

将上述所有程序放在同一个文件夹里，然后直接编译运行 grader.cpp。

上述交互库将从标准输入按照以下格式输入数据：

• 第一行， $4$ 个非负整数 $testid,n,m,x$ ，含义如题面所属，其中 $testid$ 决定交互库是否会进行对标识点编号的随机打乱，具体参见”数据范围“部分；
• 接下来 $m$ 行，每行 $2$ 个非负整数 $u[i],v[i]$ ，描述一条道路。

请务必确保输入数据格式符合题面以及”数据范围“部分的要求，否则交互库可能出现意想不到的错误。

上述交互库会将你的程序运行正确与否的相关信息输出至标准输出。

注意：上述交互库运行过程中会创建并使用文件 treasure.tmp。

你可以适当修改 grader.cpp来实现交互库向文件的输入输出。

样例

输入

1 3 2 0
0 1
1 2

输出

Correct.
cnt = 1

解释

以下是一个并不保证正确，但可能通过本例的编码和解码程序实现。你可以参照这一实现熟悉交互库的使用方法。

void Alice(const int testid, const int n, const int m, const int x, const int u[], const int v[], bool dir[])
{
    dir[0] = true;
    for(int i = 1; i < m; ++i)
        dir[i] = false;
}

int Bob(const int testid, const int n)
{
    vector<pair<int,bool>> e = discover(0); 
    return 0;
}

当标识点的编号不进行随机打乱时，该程序可通过本样例，且调用 discover(0)的返回值 $e$ 的信息如下： $e.size()$ 为 $1$ ， $e[0].first$ 为 $1$ ，$e[0].second$ 为 $true$ 。

评分标准

本题共 $25$ 个子任务，每个子任务满分 $4$ 分，由多个测试点组成。

对于每个测试点，如果你的程序不能正常结束，或 Bob函数的返回值不正确（即不是重新标号后的藏宝地点），或调用了超过 $5\times 10^5$ 次 discover函数，或调用 discover函数不符合题目要求，或有其他违反题目要求的行为，将得 $0$ 分；否则你的得分将由该测试点调用 discover函数的次数 $cnt$ 决定：

$cnt \leq5000$ ： $4$ 分；

$5000 < cnt \leq 10^4$ ： $3$ 分；

$10^4 < cnt \leq 5 \times 10^4$ ： $2$ 分；

$5\times 10^4 < cnt \leq 5 \times 10^5$ ： $1$ 分；

$cnt > 5\times 10^5$ ： $0$ 分。

你在每个子任务的得分是该子任务中所有测试点得分的最小值。

数据范围

对于所有测试点，保证 $2\leq n\leq 10^6，n-1\leq m\leq 2\times 10^6，0 \leq u[i],v[i],x \lt n$ ，给出的地图为无自环无重边的连通图，且每个环的大小均为偶数。

提示

本题时限 $5s$ ，空间限制 $1024MB$ 。保证对于任何合法的数据及在限制范围内的调用，交互库运行所用的时间不会超过 $2s$ ，运行所用的空间不会超过 $256MB$ ，也就是说，你实际可用的时间至少为 $3s$ ，实际可用的空间至少为 $768MB$ 。但需要注意的是，对于每个测试点，你的 Alice 函数和 Bob 函数所用时间和空间将会合并计算。

交互库正常运行需包含的头文件已经给出，你的程序可以包含你需要的头文件。

注意交互库使用了 using namespace std，你的程序需小心可能的变量名冲突问题。

为符合选手本地调试和评测的实际情况，本题实际评测使用的交互库与下发的交互库不完全相同。这可能导致下发交互库在输入数据规模较大时运行较慢，请不必担心。

你的程序不能进行任何读入、输出和文件操作。

通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为，所得分数无效。