luogu#P9923. [POI 2023/2024 R1] Przyciski

[POI 2023/2024 R1] Przyciski

题目背景

译自 XXXI Olimpiada Informatyczna - I etap Przyciski

题目描述

一个 n×nn\times n 的方阵,里面有 mm 个按钮。

你需要按下若干个(至少一个)按钮,使得每行每列被按下的按钮个数奇偶性相同。

输入格式

第一行两个正整数 n,mn,m

接下来 mm 行,每行两个正整数,表示一个按钮的坐标。

输出格式

如果无解,输出一行 NIE

如果有解,第一行输出 TAK,第二行输出一个正整数 kk,表示按下按钮的个数,第三行输出若干个正整数,表示你按下的按钮的编号。

3 6
1 1
1 2
2 2
3 1
3 2
3 3

TAK
4
1 2 4 5

9 1
1 1

NIE

见附件
TAK
4
1 2 10 11

见附件
TAK
4
1 2 100001 100002

提示

样例一解释:R1=2,R2=0,R3=2,C1=C2=2,C3=0R_1=2,R_2=0,R_3=2,C_1=C_2=2,C_3=0

对于所有的数据,1n1000001\leq n\leq 1000001mmin(n2,500000)1\leq m\leq\min(n^2,500000)

子任务编号 附加限制 分值
1 m20m\leq 20 24
2 如果有解,保证存在偶数解
3 如果有解,保证存在奇数解
4 28

如果有解并且你指出有解但是构造错误,你能得到 50%50\% 的分数。