奥斯塔普·本德 (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