Description

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.

Input Format

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.

Output Format

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.

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

excited  
excited  
excited  
naive  
excited  
excited  

Hint

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