3955: 「LibreOJ β Round」ZQC 的截图

一个阳光明媚的午后，ZQC 在水 QQ 群，突然他发现一位神犇发了一条装弱消息，机智的 ZQC 立即截图保存。接着，不出 ZQC 所料，群里发生了著名的“无穷递降装弱效应”。“无穷递降装弱效应”是指一位神犇装弱后，只要有一个人截图，就会发生大量的人嵌套截图的现象 …… ZQC 对屏幕上不断滚动的嵌套截图消息十分感兴趣，他想让你帮他算一个东西。在这之前，他认为有必要再强调一些关于截图消息的概念： 一条截图消息 $M$ 可以由一个二元组 $ (u,M') $ 来表示，其中 $ u $ 是这条消息的发送者，$M'$ 是另一条截图消息或 $\mathrm{NIL}$。$ M'=\mathrm{NIL} $ 表示这条消息记录是最开始的装弱消息。 例如，这条消息（最开始的装弱消息）可以表示为 $ (A,\mathrm{NIL}) $：  而这条消息可以表示为 $ (B,(A,\mathrm{NIL})) $：  如果设第一条消息为 $ S=(A,\mathrm{NIL}) $，第二条消息也可以表示为 $ (B,S) $。 消息中一个人的出现次数定义如下： 设 $ f(M,v) $ 表示消息 $ M=(u,M') $ 中 $ v $ 的出现次数，则： $$ f(M,v)=\begin{cases} & M'=\mathrm{NIL}\\ f(M',v)+& M'\neq\mathrm{NIL} \end{cases} $$ 其中 $$ 这个表达式当 $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

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

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

2
-2
-2
2
2