本题不是普通标准输入输出题。选手提交的代码中只需要实现指定的 constexpr work 函数，不要编写 main 函数，也不要从标准输入读取或向标准输出输出任何内容。

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的无向图，请判断它是否连通。

当然，事情没有这么简单。你需要按照一个特殊协议编写程序：程序会被 $N$ 个机器人逐步执行，每个顶点上有一个机器人。第 $u$ 个机器人位于第 $u$ 个顶点。每一步中，每个机器人都会执行一次你实现的函数 work。这个过程会不断重复，直到程序终止。

内存

你可以使用两类内存。

1. 全局内存：所有机器人都可以读取和写入。
2. 顶点内存：每个顶点独有，只能由位于该顶点的机器人读取。它保存该顶点的所有邻居，并且在整个执行过程中不变。

全局内存由评测程序提供。

机器人执行协议

有 $N$ 个机器人，机器人 $u$ 位于顶点 $u$，其中 $1 \le u \le N$。

协议按步数 $T$ 执行。在每一步中，每个机器人都要完成以下操作：

1. 可以自由读取第 $T$ 步开始时的全局内存，以及自己所在顶点的顶点内存。也就是说，机器人 $u$ 可以读取顶点 $u$ 的所有邻居。读取次数没有限制，只要不超过时间限制。
2. 必须对全局内存执行恰好 5 次写操作。这些写入不会立刻被当前步骤中的其他机器人看到，而是在下一步 $T+1$ 才会生效。

机器人是原子执行的：每个机器人运行 work 时不会被其他机器人打断。每一步中机器人执行顺序都是随机的，并且不同步之间不保证相同。

全局内存

全局内存共有 $5N+3$ 个单元，编号为 $0,1,\dots,5N+2$。每个单元保存一个 $0$ 到 $2^{32}-1$ 之间的无符号整数。

初始时，也就是第 $T=1$ 步开始时，除以下特殊单元外，所有单元均为 $0$：

• 单元 $1$ 保存顶点数 $N$；
• 单元 $2$ 保存边数 $M$。

单元 $0$ 也有特殊含义，它用于保存你的答案。若某一步结束后，单元 $0$ 的值为 $x \ne 0$，协议立即终止：

• 若 $x=1$，表示程序判断图是连通的；
• 若 $x=2$，表示程序判断图不是连通的；
• 若 $x$ 既不是 $1$ 也不是 $2$，则答案无效。

若单元 $0$ 仍为 $0$，则继续执行下一步。

限制

• $2 \le N \le 50000$

子任务与评分

子任务	分值	附加限制
1	19	$N \le 50$
2	21	$N \le 250$
3	25	$N \le 1000$
4	3	$N \le 50000$，且图不含环
5	32	$N \le 50000$

对于每个子任务，如果你的程序在任意测试点上没有正确判断图是否连通，则该子任务得 $0$ 分。

如果协议在 $200000$ 步后仍未终止，也得 $0$ 分。

若答案正确，则该子任务得分还取决于该子任务中测试点的最大步数 $T$。得分系数为：

$$\min\left(1.0,\sqrt{\frac{2\lceil \log_2 N\rceil}{T}}\right)$$

Hydro 配置包中使用 Special Judge 按上述公式为每个测试点给出 $[0,1]$ 的部分分，并让每个子任务取最小值。

需要实现的接口

你的提交文件会被评测器当作 solution.h 引入。你需要在提交文件中给出以下定义，并实现 work 函数。

#define SET_VAL 0
#define ADD_VAL 1

#define ANSWER_CONNECTED 1
#define ANSWER_NOT_CONNECTED 2

struct MemoryOperation {
    bool type;
    unsigned int addr, val;
    constexpr MemoryOperation(
        bool type,
        unsigned int addr,
        unsigned int val
    ) : type(type), addr(addr), val(val) {}
};

constexpr std::array<MemoryOperation, 5> work(
    unsigned int u,
    unsigned int *memory,
    unsigned int memory_size,
    unsigned int *neighbours,
    unsigned int number_neighbours
);

参数含义

• u：当前机器人所在的顶点编号。
• memory：全局内存数组。
• memory_size：全局内存大小，恒等于 $5N+3$。
• neighbours：当前顶点的邻居数组。
• number_neighbours：当前顶点邻居数量，也就是 neighbours 的长度。

work 必须返回一个包含恰好 5 个 MemoryOperation 的 std::array。

写操作说明

MemoryOperation 表示一次对全局内存的写操作，共有两种类型。

赋值操作

MemoryOperation(SET_VAL, addr, val)

表示在下一步的全局内存中执行：

memory[addr] = val;

加法操作

MemoryOperation(ADD_VAL, addr, val)

表示在下一步的全局内存中执行：

memory[addr] += val;

使用 ADD_VAL 时允许无符号整数溢出，即结果按 $2^{32}$ 取模。

如果两个或更多机器人在同一步中操作同一个单元，则操作会先按照该步的机器人随机执行顺序排序，再按照 work 返回数组中的顺序执行。

关于 constexpr

work 必须是 constexpr 函数。这意味着它不应使用非 constexpr 的全局变量或函数，不应读写标准输入输出，也不应依赖运行时副作用。

可以使用局部变量、循环、条件语句，以及你自己定义的 constexpr 辅助函数或常量。

评测器会在编译期运行一个小测试，检查你的函数是否满足 constexpr 要求。如果你修改函数签名，或者实现方式不满足要求，可能会编译失败或得到 $0$ 分。

本地调试输入格式

本题真正提交时不需要处理输入输出。以下格式仅用于本地 grader 或 Hydro 内部 grader 调试。

第一行包含三个整数：

N M S

其中 $S$ 是随机种子，用于生成每一步机器人的随机执行顺序。

接下来 $M$ 行，每行两个整数 $u,v$，表示图中有一条无向边 $(u,v)$。

输出格式

选手代码不需要、也不允许向标准输出输出任何内容。

Hydro 配置中的系统 grader 会输出内部校验信息，Special Judge 会据此判断正确性和得分。

提交说明

在本配置包中，Hydro 会通过 compile.sh 将选手提交的 C++ 文件复制为 solution.h，再编译 grader.cpp。因此提交时请直接提交一个包含上述定义和 work 实现的 C++ 源文件，例如本包提供的 std.cc。

不要提交普通读入图并输出答案的程序；这种程序不符合本题协议。