Description：

一张无向图每条边有颜色，所有颜色相同的边形成二分图。 $q$ 个询问给出 $a,b$ 代表将编号为 $a$ 的边染成颜色 $b$ ，但如果染色后不能满足所有颜色相同的边内部都是二分图就不染。问你每次是否能染成功。

$n,m,q\leqslant5\times10^5,$ 颜色数 $\leqslant50$

Solution：

$CDQ$ 分治 $+$ 线段树分治。

首先可以像线段树分治的套路那样把每段拆开，也就是把每条边拆成很多段，总长度为 $q$ ，加入到线段树中，但是这里有一个问题，就是我们并不知道到每条边到底是什么颜色，但是这样保证了每一段中颜色必定是一样的，所以不会出问题，然后就像 $CDQ$ 分治那样的做法，对整棵线段树进行 $dfs$ 同时维护一个可撤销的并查集，到叶子的时候查询，并更新边的颜色。

总结一下这题就是利用线段树分治把每条边拆成 $\log n$ 段使得每段内颜色一样，然后就可以用 $cdq$ 分治解决了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,k,q;

#define MAXN 500010

struct edges

{

	int u,v;

}es[MAXN];

int last[MAXN],col[MAXN];

struct change

{

	int e,c,ans;

}c[MAXN];

#define MAXK 51

struct UFS

{

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

	int stack[MAXN],top;

	void init()

	{

		top = 0;

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

		return;

	}

	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]));}

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

	{

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

		if(p == q)return;

		if(rnk[p] > rnk[q])swap(p,q);

		g[p] = getf(a) ^ getf(b) ^ c;

		f[p] = q;stack[++top] = p;

		if(rnk[p] == rnk[q])

		{

			++rnk[q];

			stack[++top] = -q;

		}

		return;

	}

	bool check(int a,int b,int c)

	{

		if(find(a) != find(b))return true;

		return (getf(a) ^ getf(b) ^ c) == 0;

	}

	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;

	}

}s[MAXK];

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();

	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;

}

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

{

	int pos[MAXK];

	for(int i = 1;i <= k;++i)pos[i] = s[i].top;

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

	{

		s[col[*i]].merge(es[*i].u,es[*i].v,1);

	}

	if(l == r)

	{

		if(s[c[l].c].check(es[c[l].e].u,es[c[l].e].v,1))

		{

			col[c[l].e] = c[l].c;

			c[l].ans = 1;

		}

		else c[l].ans = 0;

	}

	else

	{

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

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

	}

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

	{

		s[i].reset(pos[i]);

	}

	return;

}

int main()

{

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

	for(int i = 1;i <= m;++i)scanf("%d%d",&es[i].u,&es[i].v);

	build(root,1,q);

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

	{

		scanf("%d%d",&c[i].e,&c[i].c);

		if(last[c[i].e] != 0)add(root,last[c[i].e] + 1,i,c[i].e,1,q);

		last[c[i].e] = i;

	}

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

	{

		if(last[i] != 0 && last[i] != q)

		{

			add(root,last[i] + 1,q,i,1,q);

		}

	}

	for(int i = 1;i <= k;++i)s[i].init();

	dfs(root,1,q);

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

	{

		if(c[i].ans)puts("YES");

		else puts("NO");

	}

	return 0;

}