P3767 Magic

After Xiao Y AK'd Manhattan OI, he began to study magic. A carefully constructed magic array can generate great power, but it also has very strict requirements. The strength of the magic array is related to the number of spells, but too many spells may cause conflicts. Of course Xiao Y can solve this, but he wants to test you.

The magic array consists of $N$ nodes. Each node can have one of five attributes: metal, wood, water, fire, earth. They satisfy the generate/overcome relationships.  At the beginning, there are no spells in the magic array. Each time, Xiao Y will add a spell that requires the attributes of two nodes to satisfy a generate/overcome relationship. Then you need to answer whether there exists an assignment of an attribute to each node that satisfies all the requirements. To adjust the array, Xiao Y sometimes needs to delete a previously written spell. Xiao Y thinks this problem is too easy, so he uses the ability to change the timeline, making each operation be applied on the magic array resulting right after some previous operation.

The first line contains two positive integers $N, M$, the number of nodes and the number of operations. Then follow $M$ lines, each containing four numbers describing one operation. The first number $k$ means this operation is applied to the magic array obtained right after the $k$-th operation. If $k = 0$, it is applied to the initial magic array. The second number $t$ indicates the operation type. - $t = 1$: then input $u, v$, meaning to add a spell requiring $u$ generates $v$. - $t = 2$: then input $u, v$, meaning to add a spell requiring $u$ overcomes $v$. - $t = 3$: then input $x$, meaning to delete the spell added by the $x$-th operation.

For each operation, if after the operation there exists an assignment of attributes to all nodes that satisfies all the requirements, output `excited`; otherwise, output `naive`.

For $30\%$ of the testdata, $N, M \leq 100$. For another $30\%$ of the testdata, $k_i = i - 1$. For $100\%$ of the testdata, $N, M \leq 100000$, $0 \leq k_i < i$, $u_i \neq v_i$, $1 \leq u_i, v_i \leq N$, and all delete operations are guaranteed to be valid. Translated by ChatGPT 5