You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

神犇有一个 $n$ 个节点的图。

因为神犇是神犇，所以在 $k$ 时间内有 $m$ 条边会出现后消失。

神犇要求出每一时间段内这个图是否是二分图。

这么简单的问题神犇当然会做了，于是他想考考你。

原 BZOJ4025。

输入格式

第一行三个整数 $n,m,k$。

接下来 $m$ 行，每行四个整数 $x,y,l,r$，表示有一条连接 $x,y$ 的边在 $l$ 时刻出现 $r$ 时刻消失。

输出格式

$k$ 行，第 $i$ 行一个字符串 Yes 或 No，表示在第 $i$ 时间段内这个图是否是二分图。

3 3 3
1 2 0 2
2 3 0 3
1 3 1 2

Yes
No
Yes

提示

样例说明

$0$ 时刻，出现两条边 $(1,2)$ 和 $(2,3)$。

第 $1$ 时间段内，这个图是二分图，输出 Yes。

$1$ 时刻，出现一条边 $(1,3)$。

第 $2$ 时间段内，这个图不是二分图，输出 No。

$2$ 时刻，$(1,2)$ 和 $(1,3)$ 两条边消失。

第 $3$ 时间段内，只有一条边 $(2,3)$，这个图是二分图，输出 Yes。

数据范围

$n,k = 10^5$，$m = 2\times 10^5$。$1 \le x,y \le n$，$0 \le l \le r \le k$。

注意

本题设有 hack 数据（Subtask $2$），计 $0$ 分，但若没有通过 hack 数据则不算通过本题。