Description：

$n$ 个物品，每个物品有 $5$ 种属性，属性之间有循环相生相克的关系，每次给出一条信息或者删除一条信息，每次操作在原来一个操作的基础上进行，每次操作后询问是否存在一个合理的分配属性的方案。

$1\leqslant n\leqslant 10^5$

Solution：

联想到食物链那道题，发现可以用带权并查集来维护，有撤销有删除可以用线段树分治 $+$ 并查集的经典套路，但是本题还有一个问题就是要从某个状态的基础上进行操作。

还是考虑线段树分治，我们可以把所有的操作关系抽象成一个树结构，每一个节点是一个状态，那么我们可以求出这棵树的 $dfs$ 序，这样每次操作会影响的范围就是一棵子树，他在 $dfs$ 序列上是一个区间，那么我们就可以利用这个来进行线段树分治就行了。

总结一下，这道题和一般的线段树分治都是有修改有删除，用可撤销的带权并查集维护，但是由于这道题的操作形成了一个树结构，所以可以用 $dfs$ 序转化为序列问题。遇到这种有操作基础的问题可以往树的这方面想。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

struct option

{

	int opt,k,x,y;

}p[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int dfn[MAXN],th[MAXN],tot = 0;

int siz[MAXN];

void dfs(int k)

{

	dfn[k] = ++tot;th[tot - 1] = k;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dfs(e[i].to);

		siz[k] += siz[e[i].to];

	}

	return;

}

namespace UFS

{

	int f[MAXN],g[MAXN],rnk[MAXN];

	int find(int x){return (x == f[x] ? x : find(f[x]));}

	int getf(int x){return (x == f[x] ? 0 : (g[x] + getf(f[x])) % 5);}

	int stack[MAXN],top = 0;

	void init()

	{

		for(int i = 1;i <= n;++i)f[i] = i;

		return;

	}

	void merge(int a,int b,int c)

	{

		int p = find(a),q = find(b);

		if(rnk[p] > rnk[q]){swap(p,q);swap(a,b);c = 5 - c;}

		f[p] = q;g[p] = (getf(b) - getf(a) + c + 5) % 5;

		stack[++top] = p;

		if(rnk[p] == rnk[q]){++rnk[q];stack[++top] = -q;}

		return;

	}

	int query(int a,int b)

	{

		if(find(a) != find(b))return 0x3f3f3f3f;

		return (getf(a) - getf(b) + 5) % 5;

	}

	void reset(int pos)

	{

		while(top > pos)

		{

			int k = stack[top];--top;

			if(k > 0){f[k] = k;g[k] = 0;}

			else --rnk[-k];

		}

		return;

	}

}

vector<int> c[MAXN];

int last[MAXN];

struct node

{

	int lc,rc;

	vector<int> v;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	t[rt].v.clear();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].v.push_back(k);

		return;

	}

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	return;

}

int ans[MAXN]; 

void calc(int rt,int l,int r)

{

	int pos = UFS::top;

	bool tag = false;

	using namespace UFS;

	for(vector<int>::iterator it = t[rt].v.begin();it != t[rt].v.end();++it)

	{

		if(find(p[*it].x) != find(p[*it].y))

		{

			merge(p[*it].x,p[*it].y,p[*it].opt);

		}

		else if(query(p[*it].x,p[*it].y) != p[*it].opt)

		{

			for(int i = l;i <= r;++i)ans[th[i]] = 0;

			tag = true;break;

		}

	}

	if(!tag)

	{

		if(l == r)

		{

			ans[th[l]] = 1;

		}

		else

		{

			calc(t[rt].lc,l,mid);

			calc(t[rt].rc,mid + 1,r);

		}

	}

	reset(pos);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&p[i].k,&p[i].opt);

		if(p[i].opt == 3)scanf("%d",&p[i].x);

		else scanf("%d%d",&p[i].x,&p[i].y);

		add(p[i].k,i);

	}

	dfs(0);

	for(int i = 1;i <= m;++i)--dfn[i];

	for(int i = 1;i <= m;++i)

	{

		if(p[i].opt != 3)

		{

			c[dfn[i]].push_back(-i);

			c[dfn[i] + siz[i] - 1].push_back(i);

		}

		else

		{

			c[dfn[i] - 1].push_back(p[i].x);

			c[dfn[i] + siz[i]].push_back(-p[i].x);

		}

	}

	build(root,1,m);

	memset(last,0,sizeof(last));

	for(int i = 1;i <= m;++i)

	{

		sort(c[i].begin(),c[i].end());

		for(vector<int>::iterator it = c[i].begin();it != c[i].end();++it)

		{

			if(*it < 0)

			{

				if(last[-*it] < 0)++last[-*it];

				else last[-*it] = i;

			}

			else

			{

				if(last[*it] <= 0)--last[*it];

				else

				{

					add(root,last[*it],i,*it,1,m);

					last[*it] = 0;

				}

			}

		}

	}

	UFS::init();

	calc(root,1,m);

	for(int i = 1;i <= m;++i)

	{

		if(ans[i] == 0)puts("naive");

		else puts("excited");

	}

	return 0;

}