{"problem":{"name":"D. Permutations","description":{"content":"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 li","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF736D"},"statements":[{"statement_type":"Markdown","content":"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_.\n\nHe 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.\n\n## Input\n\nThe first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 2000, _n_ ≤ _m_ ≤ _min_(_n_2, 500 000)) — 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.\n\n## Output\n\nPrint _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_».\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"CF736D","tags":["math","matrices"],"sample_group":[["2 3\n1 1\n1 2\n2 2","NO\nYES\nNO"],["3 3\n1 1\n2 2\n3 3","NO\nNO\nNO"],["3 7\n3 3\n3 1\n1 3\n1 1\n2 2\n1 2\n2 1","YES\nNO\nNO\nNO\nYES\nNO\nNO"]],"created_at":"2026-03-03 11:00:39"}}