{"problem":{"name":"[POI 2023/2024 R1] Przyciski","description":{"content":"一个 $n\\times n$ 的方阵，里面有 $m$ 个按钮。 你需要按下若干个（至少一个）按钮，使得每行每列被按下的按钮个数奇偶性相同。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9923"},"statements":[{"statement_type":"Markdown","content":"一个 $n\\times n$ 的方阵，里面有 $m$ 个按钮。\n\n你需要按下若干个（至少一个）按钮，使得每行每列被按下的按钮个数奇偶性相同。\n\n## Input\n\n第一行两个正整数 $n,m$。\n\n接下来 $m$ 行，每行两个正整数，表示一个按钮的坐标。\n\n## Output\n\n如果无解，输出一行 `NIE`。\n\n如果有解，第一行输出 `TAK`，第二行输出一个正整数 $k$，表示按下按钮的个数，第三行输出若干个正整数，表示你按下的按钮的编号。\n\n[samples]\n\n## Background\n\n译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Przyciski](https://sio2.mimuw.edu.pl/c/oi31-1/p/prz/)。\n\n## Note\n\n样例一解释：$R_1=2,R_2=0,R_3=2,C_1=C_2=2,C_3=0$。\n\n对于所有的数据，$1\\leq n\\leq 100000$，$1\\leq m\\leq\\min(n^2,500000)$。\n\n| 子任务编号 | 附加限制 | 分值 |\n| :----------: | :----------: | :----------: |\n| 1 | $m\\leq 20$ | 24 |\n| 2 | 如果有解，保证存在偶数解 | 24 |\n| 3 | 如果有解，保证存在奇数解 | 24 |\n| 4 |  | 28 |\n\n如果有解并且你指出有解但是构造错误，你能得到 $50\\%$ 的分数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9923","tags":["图论","POI（波兰）","2023","Special Judge","构造"],"sample_group":[["3 6\n1 1\n1 2\n2 2\n3 1\n3 2\n3 3\n","TAK\n4\n1 2 4 5\n"],["9 1\n1 1\n","NIE\n"],["见附件","TAK\n4\n1 2 10 11\n"],["见附件","TAK\n4\n1 2 100001 100002\n"]],"created_at":"2026-03-03 11:09:25"}}