← 返回题目列表

Codeforces · 736/D

D. 排列

中文机器翻译题面 查看原题

奥斯塔普·本德 (Ostap Bender) 担心人们开始忘记他是伟大的组合者。现在他想向他们展示他的组合学技能。现在他研究长度n的排列。他有一个包含 m 个有效对的列表,对 ai 和 bi 意味着他可以将整数 bi 放置在位置 ai 处。

他知道仅使用有效对的排列数量是奇数。现在,对于他想要找出的每一对,如果他从列表中删除这一对(并且仅删除它),有效排列的数量是否为奇数。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 2000, n ≤ m ≤ min(n2, 500 000)) - 排列中的元素数量。然后遵循 m 行,每行包含一些有效对 (ai, bi) (1 ≤ ai, bi ≤ n)。保证输入中没有任何对出现两次,并且有效排列的总数(即仅使用允许的位置元素对)是奇数。

输出

打印 m 行,每个有效对一行。如果 Ostap 删除第 i 对(且仅删除它)后剩余的有效排列数为奇数,则第 i 行应包含“YES”。否则,打印“NO”。

示例

输入 #1

2 3
1 1
1 2
2 2

输出 #1

NO
YES
NO

输入 #2

3 3
1 1
2 2
3 3

输出 #2

NO
NO
NO

输入 #3

3 7
3 3
3 1
1 3
1 1
2 2
1 2
2 1

输出 #3

YES
NO
NO
NO
YES
NO
NO