#502. 「LibreOJ β Round」ZQC 的截图

内存限制:128 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一个阳光明媚的午后,ZQC 在水 QQ 群,突然他发现一位神犇发了一条装弱消息,机智的 ZQC 立即截图保存。接着,不出 ZQC 所料,群里发生了著名的“无穷递降装弱效应”。“无穷递降装弱效应”是指一位神犇装弱后,只要有一个人截图,就会发生大量的人嵌套截图的现象 ……

ZQC 对屏幕上不断滚动的嵌套截图消息十分感兴趣,他想让你帮他算一个东西。在这之前,他认为有必要再强调一些关于截图消息的概念:

一条截图消息 M 可以由一个二元组 (u,M') 来表示,其中 u 是这条消息的发送者, M' 是另一条截图消息或 \mathrm{NIL} M'=\mathrm{NIL} 表示这条消息记录是最开始的装弱消息。

例如,这条消息(最开始的装弱消息)可以表示为 (A,\mathrm{NIL})

1.png

而这条消息可以表示为 (B,(A,\mathrm{NIL}))

2.png

如果设第一条消息为 S=(A,\mathrm{NIL}) ,第二条消息也可以表示为 (B,S)

消息中一个人的出现次数定义如下: 设 f(M,v) 表示消息 M=(u,M') v 的出现次数,则:

f(M,v)=\begin{cases} [u=v]& M'=\mathrm{NIL}\\ f(M',v)+[u=v]& M'\neq\mathrm{NIL} \end{cases}

其中 [u=v] 这个表达式当 u=v 时值为 1,否则为 0。

ZQC 终于想好要考你什么了。对于每条消息,你需要帮他算出这些:

  1. 是否这条消息中所有人的出现次数都是 3 的倍数。
  2. 如果 1 的答案是“否”,这条消息中是否只有一个人的出现次数不是 3 的倍数。
  3. 如果 2 的答案是“是”,那个人是谁。

因为屏幕上的消息是一条一条发出来的,所以你也需要一条一条依序回答。

输入格式

第一行两个正整数 n,m 表示 ZQC 所在的群里有 n(3\leq n \leq 10^6) 个成员,一共发了 m(1\leq m\leq 2\times 10^6) 条消息。
接下来 m 行每行两个正整数 u_i,M'_i ,表示第 i 条消息是 (u_i,M'_i) M'_i=0 表示 \mathrm{NIL} ,否则表示第 M'_i 条消息。保证 1\leq u_i\leq n,0\leq M'_i<i
为了体现回答的顺序性,设上次的答案为 \mathrm{lastans} ,你需要给输入的 u_i,M'_i 分别异或上 \mathrm{lastans} 之后才能得到真实的输入。对于第一次询问, \mathrm{lastans}=0 。注意,这里做异或请用 32 位有符号整数

输出格式

输出 m 行,第 i 行一个整数表示对于第 i 条消息的计算结果。
如果 1 的答案是“是”,请输出 -1
否则如果 2 的答案是“否”,请输出 -2
否则,输出一个正整数表示那个人的编号。

样例

样例输入 1

2 5
2 0
3 3
-1 -4
-1 -3
0 3

样例输出 1

2
-2
-2
2
2

样例解释 1

真实输入如下:

2 5
2 0
1 1
1 2
1 3
2 1

第 1 条消息中出现的人: \{2\} ,只有 2 的出现次数不是 3 的倍数。
第 2 条消息中出现的人: \{2,1\} 1,2 的出现次数都不是 3 的倍数。
第 3 条消息中出现的人: \{2,1,1\} 1,2 的出现次数都不是 3 的倍数。
第 4 条消息中出现的人: \{2,1,1,1\} ,只有 2 的出现次数不是 3 的倍数。
第 5 条消息中出现的人: \{2,2\} ,只有 2 的出现次数不是 3 的倍数。

样例输入 2

13 15
5 0
0 4
2 4
-5 -4
-8 -4
-7 -5
0 7
-6 -2
3 6
-3 -7
2 10
-5 -4
-4 -13
8 7
0 7

样例输出 2

5
5
-2
-1
-2
5
-1
5
-2
3
-2
-1
3
11
11

样例解释 2

真实输入如下:

13 15
5 0
5 1
7 1
5 2
7 3
7 5
5 2
5 1
6 3
3 7
1 9
5 2
3 12
11 4
11 12

数据范围与提示

出题人的关怀:由于输入规模较大,建议使用读入优化。