[POI 2023/2024 R1] Przyciski

Luogu

IDLGP9923

Time500ms

Memory256MB

DifficultyP5

图论POI（波兰）2023Special Judge构造

一个 $n\times n$ 的方阵，里面有 $m$ 个按钮。你需要按下若干个（至少一个）按钮，使得每行每列被按下的按钮个数奇偶性相同。 ## Input 第一行两个正整数 $n,m$。接下来 $m$ 行，每行两个正整数，表示一个按钮的坐标。 ## Output 如果无解，输出一行 `NIE`。如果有解，第一行输出 `TAK`，第二行输出一个正整数 $k$，表示按下按钮的个数，第三行输出若干个正整数，表示你按下的按钮的编号。 [samples] ## Background 译自 [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/)。 ## Note 样例一解释：$R_1=2,R_2=0,R_3=2,C_1=C_2=2,C_3=0$。对于所有的数据，$1\leq n\leq 100000$，$1\leq m\leq\min(n^2,500000)$。 | 子任务编号 | 附加限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | $m\leq 20$ | 24 | | 2 | 如果有解，保证存在偶数解 | 24 | | 3 | 如果有解，保证存在奇数解 | 24 | | 4 | | 28 | 如果有解并且你指出有解但是构造错误，你能得到 $50\%$ 的分数。

Samples

Input #1

Output #1

TAK
4
1 2 4 5

Input #2

9 1
1 1

Output #2

NIE

Input #3

见附件

Output #3

TAK
4
1 2 10 11

Input #4

见附件

Output #4

TAK
4
1 2 100001 100002

API Response (JSON)

{
  "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$，表示按下按钮的个数，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments