题目描述
一个阳光明媚的午后，ZQC 在水 QQ 群，突然他发现一位神犇发了一条装弱消息，机智的 ZQC 立即截图保存。接着，不出 ZQC 所料，群里发生了著名的“无穷递降装弱效应”。“无穷递降装弱效应”是指一位神犇装弱后，只要有一个人截图，就会发生大量的人嵌套截图的现象 ……
ZQC 对屏幕上不断滚动的嵌套截图消息十分感兴趣，他想让你帮他算一个东西。在这之前，他认为有必要再强调一些关于截图消息的概念：
一条截图消息
M
M 可以由一个二元组
(u,M)
(u,M′) 来表示，其中
u
u 是这条消息的发送者，
M
M′ 是另一条截图消息或
\mathrm{NIL}
NIL。
M'=\mathrm{NIL}
M′=NIL 表示这条消息记录是最开始的装弱消息。
例如，这条消息（最开始的装弱消息）可以表示为
(A,\mathrm{NIL})
(A,NIL)：
而这条消息可以表示为
(B,(A,\mathrm{NIL}))
(B,(A,NIL))：
如果设第一条消息为
S=(A,\mathrm{NIL})
S=(A,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'=NIL)
f(M,v) = f(M',v)+[u=v] (M'!=NIL)
其中
[u=v]
[u=v] 这个表达式当
u=v
u=v 时值为 1，否则为 0。
ZQC 终于想好要考你什么了。对于每条消息，你需要帮他算出这些：
是否这条消息中所有人的出现次数都是
3
3 的倍数。
如果 1 的答案是“否”，这条消息中是否只有一个人的出现次数不是
3
3 的倍数。
如果 2 的答案是“是”，那个人是谁。
因为屏幕上的消息是一条一条发出来的，所以你也需要一条一条依序回答。
输入
第一行两个正整数
n,m
n,m 表示 ZQC 所在的群里有
n(3\leq n \leq 10^6)
n(3≤n≤106) 个成员，一共发了
m(1\leq m\leq 2\times 10^6)
m(1≤m≤2×106) 条消息。
接下来
m
m 行每行两个正整数
u_i,M'_i
ui
,M
i
′
，表示第
i
i 条消息是
(u_i,M'_i)
(ui
,M
i
′
)。
M'_i=0
M
i
′
=0 表示
\mathrm{NIL}
NIL，否则表示第
M'_i
M
i
′
条消息。保证
1\leq u_i\leq n,0\leq M'_i1≤ui
≤n,0≤M
i
′
为了体现回答的顺序性，设上次的答案为
\mathrm{lastans}
lastans，你需要给输入的
u_i,M'_i
ui
,M
i
′
分别异或上
\mathrm{lastans}
lastans 之后才能得到真实的输入。对于第一次询问，
\mathrm{lastans}=0
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
【样例输入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
样例输出
【样例输出1】
2
-2
-2
2
2
【样例输出2】
5
5
-2
-1
-2
5
-1
5
-2
3
-2
-1
3
11
11
提示
样例解释 1
真实输入如下：
Click
第 1 条消息中出现的人：
\{2\}
{2}，只有
2
2 的出现次数不是
3
3 的倍数。
第 2 条消息中出现的人：
\{2,1\}
{2,1}，
1,2
1,2 的出现次数都不是
3
3 的倍数。
第 3 条消息中出现的人：
\{2,1,1\}
{2,1,1}，
1,2
1,2 的出现次数都不是
3
3 的倍数。
第 4 条消息中出现的人：
\{2,1,1,1\}
{2,1,1,1}，只有
2
2 的出现次数不是
3
3 的倍数。
第 5 条消息中出现的人：
\{2,2\}
{2,2}，只有
2
2 的出现次数不是
3
3 的倍数。
样例解释 2
真实输入如下：
Click
数据范围与提示
出题人的关怀：由于输入规模较大，建议使用读入优化。
来源/分类
hash hash表 随机化