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

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

题目描述

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

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

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

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

1.png

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

2.png

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

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

f(M,v)={[u=v]M=NILf(M,v)+[u=v]MNIL 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] 这个表达式当 u=vu=v 时值为 1,否则为 0。

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

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

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

输入格式

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

输出格式

输出 m m 行,第 i i 行一个整数表示对于第 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\},只有 22 的出现次数不是 33 的倍数。
第 2 条消息中出现的人:{2,1}\{2,1\}1,21,2 的出现次数都不是 33 的倍数。
第 3 条消息中出现的人:{2,1,1}\{2,1,1\}1,21,2 的出现次数都不是 33 的倍数。
第 4 条消息中出现的人:{2,1,1,1}\{2,1,1,1\},只有 22 的出现次数不是 33 的倍数。
第 5 条消息中出现的人:{2,2}\{2,2\},只有 22 的出现次数不是 33 的倍数。

样例输入 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

数据范围与提示

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