#P4025. 二分图

    ID: 3226 传统题 2000ms 512MiB 尝试: 3746 已通过: 839 难度: 7 上传者: 标签>CF2200提高+/省选-线段树分治可撤销并查集扩展域并查集按大小合并二分图判定可行性剪枝

二分图

题目描述

神犇有一个 nn 个节点的图。因为神犇是神犇,所以在 TT 时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了,于是他想考考你。

输入格式

输入数据的第一行是三个整数 n,m,Tn,m,T。 第 22 行到第 m+1m+1 行,每行 44 个整数 u,v,start,endu,v,start,end。第 i+1i+1 行的四个整数表示第 ii 条边连接 u,vu,v 两个点,这条边在 startstart 时刻 出现,在第 endend 时刻消失。

输出格式

输出包含 TT 行。在第 ii 行中,如果第 ii 时间段内这个图是二分图,那么输出“Yes”,否则输出“No”,不含引号。

3 3 3
1 2 0 2
2 3 0 3
1 3 1 2
Yes
No
Yes

样例说明:

00 时刻,出现两条边 1−21-2 和 2−32-3。 第 11 时间段内,这个图是二分图,输出 Yes。 11 时刻,出现一条边 1−31-3。 第 22 时间段内,这个图不是二分图,输出 No。 22时刻,1−21-2 和 1−31-3 两条边消失。 第3时间段内,只有一条边 2−32-3,这个图是二分图,输出 Yes。

数据范围

对于 100%100\% 的数据,n≤100000,m≤200000,T≤100000n\le 100000,m\le 200000,T\le 100000,1≤u,v≤n1\le u,v\le n,0≤start≤end≤T0\le start\le end\le T。