传送门

---

思路

是二分图的充要条件：图没有奇环。

考虑按时间分治，用可撤销并查集维护点到根的距离。

仍然可以用一个小trick把两点连边变成根连边，可以看这里。

每次连边时若不连通则连上，否则判一下有没有奇环。如果有输出“No”，否则不用连。

我tm把T写成m狂WA不止

---

#include<bits/stdc++.h>

namespace my_std{

	using namespace std;

	#define pii pair<int,int>

	#define fir first

	#define sec second

	#define MP make_pair

	#define rep(i,x,y) for (int i=(x);i<=(y);i++)

	#define drep(i,x,y) for (int i=(x);i>=(y);i--)

	#define go(x) for (int i=head[x];i;i=edge[i].nxt)

	#define sz 202020

	typedef long long ll;

	template<typename T>

	inline void read(T& t)

	{

		t=0;char f=0,ch=getchar();

		double d=0.1;

		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();

		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();

		if(ch=='.')

		{

			ch=getchar();

			while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();

		}

		t=(f?-t:t);

	}

	template<typename T,typename... Args>

	inline void read(T& t,Args&... args){read(t); read(args...);}

	void file()

	{

		#ifndef ONLINE_JUDGE

		freopen("a.txt","r",stdin);

		#endif

	}

//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}

}

using namespace my_std;

int n,m,T;

struct hh{int f,t;hh(int ff=0,int tt=0){f=ff,t=tt;}}edge[sz];

int fa[sz],dep[sz],f[sz];

int getfa(int x){return x==fa[x]?x:getfa(fa[x]);}

int getdis(int x){return x==fa[x]?0:f[x]^getdis(fa[x]);}

vector<hh>v[sz<<2];

#define ls k<<1

#define rs k<<1|1

#define lson ls,l,mid

#define rson rs,mid+1,r

void insert(int k,int l,int r,int x,int y,hh e)

{

	if (x>y) return;

	if (x<=l&&r<=y) return (void)v[k].push_back(e);

	int mid=(l+r)>>1;

	if (x<=mid) insert(lson,x,y,e);

	if (y>mid) insert(rson,x,y,e);

}

struct hhh{int x,y;bool s;};

void resume(stack<hhh>S){while (!S.empty()) f[fa[S.top().x]=S.top().x]=0,dep[S.top().y]-=S.top().s,S.pop();}

void solve(int k,int l,int r)

{

	stack<hhh>S;

	rep(i,0,(int)v[k].size()-1)

	{

		hh e=v[k][i];int x=e.f,y=e.t;

		int fx=getfa(x),fy=getfa(y);

		int w=getdis(x)^getdis(y)^1;

		if (fx==fy&&w) { rep(i,l,r) puts("No"); resume(S); return; }

		if (fx!=fy)

		{

			if (dep[fx]>dep[fy]) swap(fx,fy),swap(x,y);

			hhh cur=(hhh){fx,fy,0};

			fa[fx]=fy;f[fx]=w;

			if (dep[fx]==dep[fy]) ++dep[fy],cur.s=1;

			S.push(cur);

		}

	}

	if (l==r) return puts("Yes"),resume(S);

	int mid=(l+r)>>1;

	solve(lson);solve(rson);

	resume(S);

}

int main()

{

	file();

	read(n,m,T);

	rep(i,1,n) fa[i]=i;

	int x,y,l,r;

	rep(i,1,m) read(x,y,l,r),edge[i]=hh(x,y),++l,insert(1,1,n,l,r,edge[i]);

	solve(1,1,T); // orz

	return 0;

}