luogu#P9923. [POI 2023/2024 R1] Przyciski
[POI 2023/2024 R1] Przyciski
题目背景
译自 XXXI Olimpiada Informatyczna - I etap Przyciski。
题目描述
一个 的方阵,里面有 个按钮。
你需要按下若干个(至少一个)按钮,使得每行每列被按下的按钮个数奇偶性相同。
输入格式
第一行两个正整数 。
接下来 行,每行两个正整数,表示一个按钮的坐标。
输出格式
如果无解,输出一行 NIE
。
如果有解,第一行输出 TAK
,第二行输出一个正整数 ,表示按下按钮的个数,第三行输出若干个正整数,表示你按下的按钮的编号。
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
提示
样例一解释:。
对于所有的数据,,。
子任务编号 | 附加限制 | 分值 |
---|---|---|
1 | 24 | |
2 | 如果有解,保证存在偶数解 | |
3 | 如果有解,保证存在奇数解 | |
4 | 28 |
如果有解并且你指出有解但是构造错误,你能得到 的分数。