Codeforces Round 382 (Div. 1) |
---|
Закончено |
Остап Бендер обеспокоен тем, что люди уже стали забывать, что он — Великий Комбинатор, поэтому он решил срочно подтянуть свои знания по комбинаторике. Сейчас Остап изучает перестановки длины n. У него есть список из m разрешённых пар, пара ai и bi означает, что разрешается на место ai ставить число bi.
Остап знает, что количество перестановок, использующих только разрешённые пары, нечётно. Теперь он хочет для каждой пары установить, правда ли, что если удалить данную пару из списка (и только её) разрешённых, то количество подходящих перестановок по-прежнему будет нечётным.
В первой строке входных данных записаны два числа n и m (1 ≤ n ≤ 2000, n ≤ m ≤ min(n2, 500 000)) — количество элементов перестановки. Затем следуют m строк, в каждой из которых содержится некоторая разрешённая пара (ai, bi) (1 ≤ ai, bi ≤ n). Гарантируется, что никакая разрешённая пара не встречается во входных данных дважды и что количество подходящих перестановок (то есть использующих только разрешённые пары позиция-элемент) нечётно.
Выведите m строк, по одной для каждой разрешённой пары. В i-й строке выведите «YES», если после удаления i-й разрешённой пары (и только её) количество подходящих перестановок останется нечётным, и «NO» в противном случае.
2 3
1 1
1 2
2 2
NO
YES
NO
3 3
1 1
2 2
3 3
NO
NO
NO
3 7
3 3
3 1
1 3
1 1
2 2
1 2
2 1
YES
NO
NO
NO
YES
NO
NO
Название |
---|