魔法
题目背景
小 Y 在 AK 曼哈顿 OI 之后,开始研究膜法。
一个精心构造的魔法阵可以产生强大的魔力,但是也有非常严苛的要求。
魔法阵的强度与咒语的数目相关,但是咒语太多可能会产生冲突,小Y当然会解决这个问题啦,但是他想考一考你。
题目描述
魔法阵由 $N$ 个枢纽组成。
每个枢纽可以有五种属性:金、木、水、火、土。它们之间满足相生相克的关系。
![](https://cdn.luogu.com.cn/upload/pic/5349.png)
一开始,魔法阵中没有咒语。
每次,小 Y 会添加一条咒语,它会要求两个枢纽的属性满足相生/相克的关系。然后你需要回答:是否存在一种为每个枢纽分配一个属性的方案,满足所有的要求。
为了调整法阵,小 Y 有时候需要删除一条写过的咒语。
小 Y 觉得这个问题太简单了,于是他使用改变时间线的能力,让每一次操作在之前某一次操作后形成的魔法阵的基础上进行。
输入输出格式
输入格式
第一行两个正整数 $N,M$,表示枢纽的个数和操作个数。
接下来 $M$ 行,每行四个数表示一次操作。
第一个数 $k$ 表示这次操作在第 $k$ 次操作结束后的魔法阵上进行,如果 $k=0$,则表示在初始的魔法阵上进行。
第二个数 $t$ 表示操作类型。
- $t=1$:接下来输入 $u,v$,表示加入一条咒语,要求 $u$ 生 $v$。
- $t=2$:接下来输入 $u,v$,表示加入一条咒语,要求 $u$ 克 $v$。
- $t=3$: 接下来输入 $x$,表示删除第 $x$ 次操作加入的咒语。
输出格式
对于每一次操作,如果操作后存在为每个枢纽分配一个属性的方案,满足所有的要求,输出 `excited`,否则输出 `naive`。
输入输出样例
输入样例 #1
3 6
0 1 1 2
1 1 2 3
2 2 1 3
2 1 3 1
2 3 1
5 1 3 1
输出样例 #1
excited
excited
excited
naive
excited
excited
说明
对于 $30\%$ 的数据,满足 $N,M\leq 100$;
对于另 $30\%$ 的数据,满足 $k_i=i-1$;
对于100%的数据,满足 $N,M \leq 100000, 0\leq k_i < i, u_i \neq v_i, 1 \leq u_i,v_i \leq N$,保证所有删除操作都合法。