{"problem":{"name":"[CEOI 2022] Parking","description":{"content":"Valerija 在一家饭店的停车场工作，她负责礼貌地接待重要的客人，保管他们的车钥匙并帮助他们停车。 一个晚上，她发现她管理的停车场中恰好有 $2N$ 辆车，它们共有 $N$ 种不同的颜色，每种颜色恰有两辆车。我们将颜色按 $1$ 到 $N$ 编号。 停车场共有 $M$ 个车位，按 $1$ 到 $M$ 编号，每一个车位可以停下两辆车，一个车位只有一个入口，我们称靠近入口的为「顶上的车」，远离","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9001"},"statements":[{"statement_type":"Markdown","content":"Valerija 在一家饭店的停车场工作，她负责礼貌地接待重要的客人，保管他们的车钥匙并帮助他们停车。\n\n一个晚上，她发现她管理的停车场中恰好有 $2N$ 辆车，它们共有 $N$ 种不同的颜色，每种颜色恰有两辆车。我们将颜色按 $1$ 到 $N$ 编号。\n\n停车场共有 $M$ 个车位，按 $1$ 到 $M$ 编号，每一个车位可以停下两辆车，一个车位只有一个入口，我们称靠近入口的为「顶上的车」，远离入口的为「底下的车」，一辆车可以从入口开出当且仅当没有车挡着它。Valerija 在停车的时候，保证每个车位要么空，要么停满两辆车，要么只有一辆底下的车。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/q0r8s8f5.png)\n\n这张图描述的是第一个样例，同时呈现了唯一的第一次驾驶。\n\nValerija 想要重新停放车使得每一对相同颜色的车都在一个车位里。我们并不关心车位对应什么颜色以及哪辆车在顶上哪辆车在底下。Valerija 将执行如下操作：\n\n- 驾驶一辆可以驶出车位的车，将车开到另一个车位，满足：\n    - 这个车位是空的，并把车停在底下的车位，或者，\n    - 这个车位有且只有一辆与当前驾驶的车颜色相同的车。\n    \nValerija 想知道最少的操作次数与操作方案，请你解决这个问题。\n\n## Input\n\n第一行两个整数 $N,M$。\n\n接下来 $M$ 行，一行两个整数 $b_i,t_i$，$b_i$ 表示停在这个车位底下的车的颜色，$t_i$ 表示停在这个车位顶上的车的颜色，如为 $0$，则表示这个车位底下/顶上的位置没有车。\n\n## Output\n\n如果没有办法完成要求，输出一行一个整数 $-1$。\n\n否则，第一行一个整数 $K$，表示最少的操作次数。\n\n接下来 $K$ 行，一行两个整数 $x_i,y_i$，表示第 $i$ 次操作将车位 $x_i$ 中可以驶出车位的车开到车位 $y_i$。\n\n注意到最短解可能不唯一，你只需要输出任意一种即可。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n由题目描述中的图可以看出，这个样例只有唯一解。\n\n### 数据规模与约定\n\n对于全部数据，$1\\le N\\le M\\le 2\\times 10^5$。\n\n如果你的程序正确求出了最少的操作次数，但是方案构造错误，你将会获得对应点 $20\\%$ 的分数。\n\n| Subtask 编号 |                 特殊限制                  | 分数 |\n| :----------: | :--------------------------------------: | :--: |\n|     $1$      |                 $M\\le 4$                 | $10$ |\n|     $2$      |                $2N\\le M$                 | $10$ |\n|     $3$      | $N\\le 1000$，每个车位要么是空的要么是满的。 | $25$ |\n|     $4$      |       每个车位要么是空的要么是满的。        | $15$ |\n|     $5$      |               $N\\le 1000$                | $25$ |\n|     $6$      |                无特殊限制                 | $15$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9001","tags":["模拟","2022","Special Judge","CEOI（中欧）","图论建模","栈"],"sample_group":[["4 5\n1 0\n2 0\n1 3\n4 4\n3 2","3\n5 2\n3 5\n3 1"],["4 5\n0 0\n2 1\n3 1\n3 4\n2 4","-1"],["5 7\n1 0\n2 1\n2 3\n4 3\n5 4\n5 0\n0 0","6\n2 1\n3 7\n4 7\n2 3\n5 4\n5 6"]],"created_at":"2026-03-03 11:09:25"}}