题目类型说明

这是一道提交函数题。

你需要提交一个源文件，实现指定函数；评测时你的程序会与评测器一同编译运行。
不要实现 main 函数，不要从标准输入读入，也不要向标准输出输出。

你需要包含头文件：

#include "subway.h"

---

题目描述

在保加利亚东北部发生了一次大迁徙后，Radko Dimitrievo 村的村长必须应对村庄的迅速扩张。他在竞选时曾承诺要给村里修建地铁，现在必须兑现这个承诺。

经过长时间思考，村长选定了 N 个不同的地铁站，编号为 0 到 N - 1。此外，还会修建 M 条有向隧道，编号为 0 到 M - 1。其中第 i 条隧道从车站 A_i 出发，到达车站 B_i（允许 A_i = B_i）。

村里有 D 家地铁列车公司，编号为 0 到 D - 1。每条隧道必须恰好由一家公司负责运营。每家公司都希望运营若干条环线，使得每个车站都恰好出现在这些环线中的某一条里。

这里，“环线”指的是一串隧道，满足：

• 每条隧道的终点是下一条隧道的起点；
• 最后一条隧道的终点是第一条隧道的起点；
• 在线路中，每个车站恰好作为某条隧道的起点一次，并且恰好作为某条隧道的终点一次。

为了使这一要求有可能实现，题目保证：

• 每个车站恰好有 D 条隧道从它出发；
• 每个车站恰好有 D 条隧道到达它。

注意，这意味着：

$$M = N \cdot D$$

你的任务是：若存在可行分配，则给出一种把隧道分配给各家公司的方案；否则输出不可能。

---

实现要求

你需要实现函数：

bool assign_roads(int N, int M, vector<int> A, vector<int> B)

该函数会被调用恰好一次。传入参数 N、M 以及数组 A、B，它们描述了 M 条隧道的起点和终点。

函数执行结束时：

• 如果存在可行方案，则返回 true；
• 否则返回 false。

如果你的函数返回 true，那么在返回之前，你必须恰好调用 D 次评测器提供的辅助函数 answer，每家公司恰好调用一次：

void answer(int company_id, vector<int> roads)

其中：

• company_id 表示公司编号；
• roads 表示你分配给这家公司的隧道编号列表。

你的程序将与评测器一起编译。
不要实现 main 函数，不要读写标准输入输出。
你必须包含头文件 subway.h。题目会提供本地评测器和头文件，便于你本地测试。

---

限制

• 1 ≤ N ≤ 30000
• 1 ≤ D ≤ 30000
• 1 ≤ M ≤ 1210000
• 0 ≤ A_i, B_i ≤ N - 1（注意允许 A_i = B_i）

---

子任务

子任务	分值	N	D	M
1	8	≤ 5	≤ 4	≤ 16
2	9		≤ 5000	≤ 25000
3	16	≤ 30000	= 2	≤ 60000
4	21			≤ 1210000
5	13	≤ 350		≤ 2000
6	10			≤ 122500
7	5	≤ 4000	≤ 70	≤ 280000
8	6	≤ 500	≤ 1500	≤ 600000
9		≤ 1100		≤ 1210000
10		≤ 30000

某个子任务的分数，只有在该子任务及其包含的所有更弱限制子任务全部通过时才能获得。

对于子任务 4，其限制中提到的 K 是任意正整数，并满足：

$$2K \le 30000$$

---

样例

在样例中：

• N = 4
• D = 3
• M = 12

隧道依次为：

(0, 1), (1, 2), (2, 0), (3, 3),
(0, 1), (1, 0), (2, 3), (3, 2),
(0, 2), (3, 1), (1, 0), (2, 3)

评测器会调用：

assign_roads(
    4, 12,
    {0, 1, 2, 3, 0, 1, 2, 3, 0, 3, 1, 2},
    {1, 2, 0, 3, 1, 0, 3, 2, 2, 1, 0, 3}
)

在这个例子中，可行方案是存在的，因此函数应返回 true。不过在返回之前，必须调用 answer 共 3 次。下面是一组合法的调用方式：

answer(0, {0, 1, 2, 3});
answer(1, {4, 5, 6, 7});
answer(2, {8, 9, 10, 11});