题解：
首先关于二分图的性质， 就是没有奇环边。 题目其实就是让你判断每个时段之内有没有奇环。
其次 lct 只能维护树，(反正对于我这种菜鸟选手只会维护树)， 那么对于一棵树来说， 填上一条边会形成奇数环，或者偶数环。
现在我们考虑偶数环， 对于偶数环来说， 如果加上一条边都能使得这个图出现一个奇数环， 我们现在任意删除一条边，都还是会存在一个奇数环。
那么当出现偶数环的情况下， 我们可以删除一条边， 保存树的性质。
当出现奇数环的时候， 我们也需要删除某一条边， 并且需要标记被树上删除的那个边是什么边，直到那个边消失之前， 这个图就存在奇数环。
我们现在按照边的消失的时间从小到大删除边。 因为找替换边太麻烦了， 不好处理。 我们按照消失的时间处理之后， 就一定不会存在替换的边。
删除的时候， 也要顺带删除掉标记。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("2.in","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 5e5 + ;
struct Node{
int rev, rt, sz;
int son[], pre;
int t, tt, id;
void init(){
sz = rt = ; rev = pre = son[] = son[] = ;
tt = t = inf;
}
}tr[N];
void Push_Rev(int x){
if(!x) return ;
swap(lch(x), rch(x));
tr[x].rev ^= ;
}
void Push_Up(int x){
if(!x) return ;
tr[x].sz = tr[lch(x)].sz + tr[rch(x)].sz + ;
tr[x].id = x;
tr[x].tt = tr[x].t;
if(tr[x].tt > tr[lch(x)].tt) tr[x].id = tr[lch(x)].id, tr[x].tt = tr[lch(x)].tt;
if(tr[x].tt > tr[rch(x)].tt) tr[x].id = tr[rch(x)].id, tr[x].tt = tr[rch(x)].tt;
}
void Push_Down(int x){
if(tr[x].rev){
tr[x].rev = ;
Push_Rev(lch(x));
Push_Rev(rch(x));
}
}
void Rev(int x){
if(!tr[x].rt) Rev(tr[x].pre);
Push_Down(x);
}
void rotate(int x){
if(tr[x].rt) return;
int y = tr[x].pre, z = tr[y].pre;
int k = (rch(y) == x);
tr[y].son[k] = tr[x].son[k^];
tr[tr[y].son[k]].pre = y;
tr[x].son[k^] = y;
tr[y].pre = x;
tr[x].pre = z;
if(tr[y].rt) tr[y].rt = , tr[x].rt = ;
else tr[z].son[rch(z) == y] = x;
Push_Up(y);
}
void Splay(int x){
Rev(x);
while(!tr[x].rt){
int y = tr[x].pre, z = tr[y].pre;
if(!tr[y].rt){
if(( x == rch(y) ) != (y == rch(z))) rotate(y);
else rotate(x);
}
rotate(x);
}
Push_Up(x);
}
void Access(int x){
int y = ;
do{
Splay(x);
tr[rch(x)].rt = ;
rch(x) = y;
tr[y].rt = ;
Push_Up(x);
y = x;
x = tr[x].pre;
}while(x);
}
void Make_rt(int x){
Access(x);
Splay(x);
Push_Rev(x);
}
void link(int u, int v){
Make_rt(u);
tr[u].pre = v;
}
void cut(int u, int v){
Make_rt(u);
Access(v);
Splay(v);
tr[lch(v)].pre = ;
tr[lch(v)].rt = ;
tr[v].pre = ;
lch(v) = ;
}
bool judge(int u, int v){
while(tr[u].pre) u = tr[u].pre;
while(tr[v].pre) v = tr[v].pre;
return u == v;
}
int n, m, u, v, st, ed, T, id, odd, t;
int tot;
int vis[N], in[N];
struct node{
int u, v, id, t, t2;
bool operator < (const node & x) const {
if(t != x.t) return t < x.t;
return t2 < x.t2;
}
}A[N];
void add(int u, int v, int id, int t, int t2){
++tot;
A[tot].u = u; A[tot].v = v; A[tot].id = id;
A[tot].t = t; A[tot].t2 = t2;
}
int main(){
tr[].tt = tr[].t = inf;
scanf("%d%d%d", &n, &m, &T);
for(int i = ; i <= n+m; i++)
tr[i].init();
for(int i = ; i <= m; i++){
scanf("%d%d%d%d", &u, &v, &st, &ed);
tr[i+n].t = ed;
if(st == ed) continue;
add(u, v, n+i, st, ed);
add(u, v, n+i, ed, -);
}
sort(A+, A++tot);
int j = ;
for(int i = ; i < T; i++){
while(j <= tot && A[j].t == i){
u = A[j].u, v = A[j].v, id = A[j].id, t = A[j].t2;
if(t == -){
if(in[id]){
cut(u, id);
cut(v, id);
}
odd -= vis[id];
}
else {
if(u == v) {
vis[id] = ;
odd++;
}
else {
if(!judge(u, v)){
link(u, id);
link(v, id);
in[id] = ; }
else {
Make_rt(u);
Access(v);
Splay(v);
int sz = tr[v].sz / ;
int p = tr[v].id;
int tt = tr[v].tt;
if(tt >= t){
if(sz% == ){
odd++;
vis[id] = ;
}
}
else {
if(sz% == ){
odd++;
vis[p] = ;
}
cut(u, p);
cut(v, p);
in[p] = ;
link(u, id);
link(v, id);
in[id] = ;
}
}
} }
j++;
}
if(odd) puts("No");
else puts("Yes");
}
return ;
}
