#A. [POI 2023/2024 R1] Przyciski

    Type: RemoteJudge 500ms 256MiB

[POI 2023/2024 R1] Przyciski

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 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\% 的分数。

周四下午训练

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2025-2-20 8:00
End at
2025-2-20 17:00
Duration
9 hour(s)
Host
Partic.
6