← 返回题目列表

Codeforces · 566/D

D. 重组公司

中文机器翻译题面 查看原题

即使是最成功的公司也会经历危机时期,你必须做出艰难的决定——重组、放弃和合并部门、解雇员工以及做其他不愉快的事情。让我们考虑以下公司模型。

有 n 个人在大型软件公司工作。每个人都属于某个部门。最初,每个人在自己的部门从事自己的项目(因此,每个公司最初由 n 个部门组成,每个部门一个人)。

然而,公司的困难时期已经到来,管理层不得不聘请一位危机经理来重建工作流程以提高效率。让我们使用 team(person) 来表示 person person 工作的团队。危机管理者可以做出两种类型的决策:

1. 将部门 team(x) 和 team(y) 合并为一个大部门,其中包含 team(x) 和 team(y) 的所有员工,其中 x 和 y (1 ≤ x, y ≤ n) — 是公司部分员工中两人的编号。如果 team(x) 与 team(y) 匹配,则不会发生任何事情。
2. 合并部门 team(x), team(x + 1), ..., team(y),其中 x 和 y (1 ≤ x ≤ y ≤ n) — 公司中某两名员工的人数。

危机经理有时会想知道员工 x 和 y (1 ≤ x, y ≤ n) 是否在同一部门工作。

帮助危机经理并回答他的所有疑问。

输入

输入的第一行包含两个整数 n 和 q (1 ≤ n ≤ 200 000, 1 ≤ q ≤ 500 000) — 公司员工人数和危机经理的查询数量。

接下来 q 行包含危机经理的查询。每个查询看起来都类似于 x y 类型,其中 $$type \in \{1, 2, 3\}$$。如果type=1或type=2,则查询代表危机管理者关于分别合并第一类型和第二类型的部门的决定。如果 type = 3,则您的任务是确定员工 x 和 y 是否在同一部门工作。请注意,在任何类型的查询中 x 都可以等于 y。

输出

对于类型 3 的每个问题,打印“是”或“否”(不带引号),具体取决于相应的人员是否在同一部门工作。

示例

输入 #1

8 6
3 2 5
1 2 5
3 2 5
2 4 7
2 1 2
3 1 7

输出 #1

NO
YES
YES