题目描述

Natali 喜欢高速运动，决定在保加利亚最大、最现代化的游乐园度过一个下午。这个游乐园位于大特尔诺沃，今天刚刚首次向游客开放。

由于摩天轮、贡多拉和碰碰车对她这种冒险性格来说太无聊了，她决定直接去玩“肾上腺素过山车”。

这座过山车非常现代。它由 $N$ 个站点组成，编号为 $1$ 到 $N$。从每个站点恰好有一条单向轨道通向其他 $N-1$ 个站点中的某一个。

站点分为三种：

• 红色站点：从该站点出发，沿着单向轨道经过若干个（大于 $0$ 个）其他站点后，最终可以再次回到该站点；
• 黄色站点：该站点不是红色站点，但从它出发的单向轨道直接通向一个红色站点；
• 绿色站点：所有其他站点都是绿色站点。

一次乘坐必须从绿色或黄色站点开始，并在红色站点结束。过程中不能经过同一个站点超过一次，即使是终点也不能重复经过。

经过每条站点之间的轨道时，会获得一定数量的肾上腺素。这个数值可以是正数，也可以是负数。

这座过山车的一个绝对创新点是：工作人员会不时改变轨道网络结构，使它变得更刺激。允许的改变非常特殊：选择两个黄色站点，交换从它们出发的轨道所指向的红色终点。在交换时，从这两个黄色站点出发的轨道所带来的肾上腺素值保持不变。

Natali 来到过山车前，并想尝试不同路线。她每次会选择一个红色站点 $F$ 作为目标终点，并提出问题：她应该从哪个黄色或绿色站点开始乘坐，才能最终到达编号为 $F$ 的站点，并且一路获得的肾上腺素总量至少为 $K$？当然，这样的起点可能不存在。

你的任务是编写函数 solve()，它会与评测程序一起编译，并需要处理 $Q$ 个请求：

• 类型 1：Natali 的询问，要求确定一次乘坐的起点；
• 类型 2：工作人员改变轨道结构的请求。

实现细节

你需要实现如下函数：

void solve(int N, int Q, int *next, int *weight);

该函数会被评测程序调用一次。参数含义如下：

• N：站点数；
• Q：请求数；
• next[]：初始轨道结构数组。next[i]（$0 \le i < N$）表示从编号为 $i+1$ 的站点出发的单向轨道所到达的站点编号。

注意：不要混淆 next 数组的下标（从 $0$ 到 $N-1$）与站点编号（从 $1$ 到 $N$）。

• weight[]：轨道上的肾上腺素值数组。weight[i] 表示经过从编号为 $i+1$ 的站点出发的轨道时获得的肾上腺素量。

交互函数

为了与评测程序通信，提供如下函数：

int getQuery(long long *arg0, long long *arg1);

你必须调用该函数 $Q$ 次，每次调用会获得一个需要处理的请求。

类型 1 请求

如果 getQuery() 返回 1，这是 Natali 的询问：

• arg0 是她想要到达的红色站点编号；
• arg1 是她希望获得的最小肾上腺素总量。

你需要调用如下函数回答：

void answerQuery(int answerType, int answer);

如果不存在满足要求的起点，应调用：

answerQuery(0, -1);

如果存在，应调用：

answerQuery(1, start);

其中 start 是一个合法起点编号，满足 $1 \le start \le N$。

类型 2 请求

如果 getQuery() 返回 2，这是工作人员改变轨道结构的请求。此时：

• arg0 和 arg1 是两个黄色站点的编号；
• 需要交换从这两个黄色站点出发的轨道所指向的红色终点；
• 不需要调用 answerQuery()，只需在程序内部完成这次修改。

提交要求

你需要提交文件 park.cpp。该文件可以包含实现 solve() 所需的其他代码，但不能包含 main()。

文件开头必须包含：

#include "park.h"

数据范围

• $|weight[i]| \le 1\,000\,000\,000$。

其他限制见子任务。

样例说明

原题给出了一组完整的调用过程示例。该示例中：

评测程序调用你的函数：

N = 10, Q = 7
next:   5 9 9 1 10 2 1 5 3 1
weight: 8 -6 6 8 0 -2 9 -7 -5 -7

初始网络如原题图 1 所示。站点 $1,3,5,9,10$ 是红色站点，站点 $2,4,7,8$ 是黄色站点，站点 $6$ 是唯一的绿色站点。

接下来依次处理如下请求：

步骤	请求 / 操作	合法回答示例	说明
1	初始调用 solve()	-	参数如上
2	类型 1，arg0=5,arg1=20	answerQuery(0,-1)	不存在满足条件的起点
3	类型 1，arg0=5,arg1=17	answerQuery(1,7)	从 $7$ 出发，路径为 $7\to1\to5$
4	类型 1，arg0=3,arg1=-20	answerQuery(1,6)	从 $6$ 出发，路径为 $6\to2\to9\to3$
5	类型 1，arg0=9,arg1=2	answerQuery(0,-1)	当前网络下不存在满足条件的起点
6	类型 2，arg0=2,arg1=4	不回答	交换黄色站点 $2$ 和 $4$ 出边所指向的红色终点，网络变为原题图 2
7	类型 1，arg0=9,arg1=2	answerQuery(1,4)	从 $4$ 出发，路径为 $4\to9$
8	类型 1，arg0=1,arg1=-20	answerQuery(1,6)	从 $6$ 出发，路径为 $6\to2\to1$

原题包含图 1 和图 2，分别表示修改前后的轨道网络结构。Hydro 题面整理时请在此处自行补入对应图片。

子任务

子任务	分值	$N$	$Q$	备注
1	2	$\le 1000$	$\le 100$	无类型 2 请求
2	3		$\le 50000$
3	7	$\le 50000$
4	17	$\le 500000$
5	3	$\le 1000$	$\le 100$	-
6	5		$\le 10000$
7	21	$\le 50000$
8	42	$\le 500000$

本地测试

原题提供 Lgrader.cpp 和 park.h 用于本地测试。将它们与你的 park.cpp 一起编译，可以得到一个处理请求列表的可执行程序。

本地 grader 的输入格式如下：

第一行输入 $N,Q$。

第二行输入数组 next。

第三行输入数组 weight。

接下来 $Q$ 行，每行输入一个请求，格式为：

queryType arg0 arg1

其中 queryType 为 1 或 2，含义与上文一致。

本地 grader 输出格式如下：

第一行输出请求数 $Q$。

对于每个类型 1 请求，输出一行：

• 若不存在路径，输出 0；
• 否则输出 1 x，其中 x 是你的函数找到的起点。

对于每个类型 2 请求，输出一行 2。