#569. BZOJ 4025. 二分图

BZOJ 4025. 二分图

题目描述

神犇有一个 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 时刻,出现两条边 121-2232-3。 第 11 时间段内,这个图是二分图,输出 Yes11 时刻,出现一条边 131-3。 第 22 时间段内,这个图不是二分图,输出 No22时刻,121-2131-3 两条边消失。 第3时间段内,只有一条边 232-3,这个图是二分图,输出 Yes

数据范围

对于 100%100\% 的数据,n100000,m200000,T100000n\le 100000,m\le 200000,T\le 1000001u,vn1\le u,v\le n0startendT0\le start\le end\le T