Permutations

题意翻译

## 题目描述 奥斯塔普·本德 (Ostap Bender) 开始忧心忡忡，因为人们已经开始逐渐忘记他是伟大的组合学带师。现在，他想秀一下自己高超的组合技术。 现在，他正研究着长度为 $n$ 的排列。另外。他还有 $m$ 个限制，第 $i$ 个限制可以表示成数对 $(a_i, b_i)$，代表排列中的第 $a_i$ 个位置可以是 $b_i$。 现在他已经知道，满足所有限制的排列数量有奇数个。而他想知道的是，对于每一个限制，在去掉（且仅去掉）它之后，满足所有限制的排列数量是否仍然是奇数个。 ## 输入格式 第一行 2 个整数 $n, m$ （$1 \leq n \leq 2000; n \leq m \leq \mathrm{min}(n^2, 500000)$）。$n$ 是排列的长度，而 $m$ 是限制的数量。 接下来有 $m$ 行，每行两个数 $a_i, b_i$，代表一组限制 $(a_i, b_i)$。 输入中的限制不会重复。 满足所有限制的排列数量一定是奇数个。 ## 输出格式 输出 $m$ 行，对于第 $i$ 行，如果奥斯塔普·本德在去掉第 $i$ 组限制之后，满足所有限制的排列数量还是奇数个，那么这一行是 `YES`，否则是 `NO`。

题目描述

Ostap Bender is worried that people started to forget that he is the Great Combinator. Now he wants to show them his skills in combinatorics. Now he studies the permutations of length $ n $ . He has a list of $ m $ valid pairs, pair $ a_{i} $ and $ b_{i} $ means that he is allowed to place integers $ b_{i} $ at position $ a_{i} $ . He knows that the number of permutations that use only valid pairs is odd. Now, for each pair he wants to find out, will the number of valid permutations be odd if he removes this pair (and only it) from the list.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n<=2000 $ , $ n<=m<=min(n^{2},500000) $ ) — the number of elements in the permutation. Then follow $ m $ lines, each containing some valid pair $ (a_{i},b_{i}) $ ( $ 1<=a_{i},b_{i}<=n $ ). It's guaranteed that no pair occurs in the input twice and that the total number of valid permutations (i.e. using only allowed pairs position-elements) is odd.

输出格式

Print $ m $ lines, one line for each valid pair. The $ i $ -th line should contain "YES" if after Ostap removes the $ i $ -th pair (and only it) the remaining number of valid permutations is odd. Otherwise, print «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