Description

冒险计划

你正在为一次冒险做准备。这次冒险是在一个有向无环图（DAG）上的从起点到终点的旅程。该 DAG 有 $n$ 个顶点，编号为 $0$ 到 $n-1$，以及 $m$ 条边。起点是顶点 $0$，且所有顶点都可从起点到达。

每条从 $u_i$ 到 $v_i$ 的有向边都有两个属性：$l_i$ 和 $r_i$。它表示安全通过该边所需的最小和最大时间。因此，你可以为该边设定计划通过时间 $t_i$，满足 $t_i$ 是区间 $[l_i, r_i]$ 内的任意整数。

你的许多朋友也正在为冒险做准备。每个人都会选择一条不同的从起点到终点的路径。为了保证安全，你希望选择每条边的计划通过时间，使得从起点到任意顶点 $u$ 的所有路径消耗的总时间都相同。也就是说，希望对每个顶点 $u$，所有从起点到 $u$ 的路径，它们的总用时都一样。

我们称图满足上述要求时为“安全”的。保证初始的图是安全的。

任务 1

你想向图中添加一些新边，使其更加有趣。你将执行 $q$ 次“添加新边”的操作。每次操作会给出一条新的有向边 $(u_i, v_i, l_i, r_i)$。你已知添加这条边后，图依然是有向无环图，但不确定图是否仍然安全。请判断添加该边后图是否安全。如果安全，就将该边添加到图中；否则，忽略这次操作。

任务 2

所有操作结束后，你需要为每条边（包括新增边）输出一个计划通过时间 $t_i$，以证明你能确保新图依然安全。

实现细节

你需要实现两个过程：

第一个过程是 add_roads：

boolean[] add_roads(int32 N, int32 M, int32 Q,
                    int32[] U, int32[] V,
                    int32[] L, int32[] R,
                    int32[] U2, int32[] V2,
                    int32[] L2, int32[] R2);

• $N$：顶点数；
• $M$：初始边数；
• $Q$：操作数；
• $U, V$：长度为 $M$ 的数组，第 $i$ 条有向边为 $(U[i], V[i])$；
• $L, R$：长度为 $M$ 的数组，第 $i$ 条边的可选时间区间为 $[L[i], R[i]]$；
• $U2, V2, L2, R2$：长度为 $Q$ 的数组，描述每个新添加的边；
• 本过程在每个测试用例开始时恰好调用一次。

本过程需返回一个长度为 $Q$ 的数组，第 $i$ 个元素为 true 当且仅当执行第 $i$ 次操作时将该边添加进图，否则为 false。

第二个过程是 assign_times：

int32[] assign_times();

• 本过程在每个测试用例的 add_roads 调用结束后恰好调用一次。

本过程需返回一个数组，依次给出最终图中每条边的计划时间 $t_i$（输出顺序任意合法即可）。

Input Format

无特殊输入格式说明，见样例与题目描述。

Output Format

无特殊输出格式说明，见样例与题目描述。

Hint

样例

样例 1

考虑如下调用：

add_roads(4, 4, 2,
          [0, 1, 0, 0],
          [1, 3, 3, 2],
          [1, 3, 9, 6],
          [5, 7, 14, 8],
          [2, 2],
          [3, 3],
          [7, 5],
          [11, 7]);

该过程应返回 [false, true]。

在 add_roads 调用后，若输入：

assign_times();

应返回 [5, 7, 12, 6, 6]。

样例评测器

样例评测器将输入数据读入格式如下：

• 第 1 行：三个整数 $n, m, q$
• 接下来的 $m$ 行：每行四个整数 $u_i, v_i, l_i, r_i$，描述一条初始边
• 接下来的 $q$ 行：每行四个整数 $u_i, v_i, l_i, r_i$，描述一次操作

提示

• $3 \le n \le 500$
• $n-1 \le m \le 10^5$
• $0 \le q \le 500$
• $0 \le u_i < n$
• $1 \le l_i \le r_i \le 10^9$

评分

1. 子任务 1（7 分）：$n \le 3$
2. 子任务 2（21 分）：$q = 0$
3. 子任务 3（12 分）：$v_i = u_i + 1$
4. 子任务 4（11 分）：$l_i = r_i$
5. 子任务 5（24 分）：$n \le 100, m \le 100, q \le 100$
6. 子任务 6（25 分）：无额外约束。

由 ChatGPT 5 翻译