在世界各地的编程竞赛中，设置一道好的竞赛题目并非易事。其中一个挑战在于测试数据的设置。好的测试数据应当能够区分出符合要求的代码，与那些虽然看起来正确但在某些特殊情况下会失败的代码。

在本题中，你在竞赛中的角色发生了反转！作为一名经验丰富的程序员，你正在协助“快乐程序员竞赛”（Happy Programmer Contest）委员会设置他们的测试数据。委员会选择了两个图论问题，总共包含 8 个不同的子任务，并编写了一些看起来能解决这些图论问题的代码。在设计子任务时，委员会的意图是让部分代码能够获得满分，而另一些代码则只能获得零分或部分分数。你将获得所有这些代码的 C、C++ 和 Pascal 版本。对于每个子任务，你的工作是生成一个测试数据 $X$，用以区分给定的两个代码：代码 A 和代码 B。更具体地说，必须满足以下两个条件：

1. 对于输入 $X$，代码 A 不能导致超时（Time Limit Exceeded, TLE）。
2. 对于输入 $X$，代码 B 必须导致超时。

此外，委员会倾向于较小的测试数据，目标是测试数据中的整数个数不超过 $T$ 个。

委员会选择的两个问题分别是单源最短路径（Single-Source Shortest Paths, SSSP）问题，以及一个我们称之为“神秘”（Mystery）的图论问题。委员会编写的代码的伪代码列在附录中，C、C++ 和 Pascal 的实现可以在随任务 3 提供的压缩包中找到。

子任务

请参考表 1。每一行描述一个子任务。注意，子任务 1 到 6 是关于 SSSP 问题的，而子任务 7 和 8 是关于 Mystery 问题的。各子任务分配的分数在 $S$ 列中列出。

表 1：8 个子任务。

要获得子任务的任何分数，你的测试数据 $X$ 必须能够区分相应的代码 A 和代码 B。此外，你获得的分数取决于 $X$ 中有符号整数的个数。假设 $X$ 包含 $F$ 个整数，该子任务分配的分数为 $S$，且 $T$ 为目标规模，则奖励分数的计算方式如下：

$\lfloor (S/100) \times \min(100 \times T/F, 100) \rfloor$

其中 $\lfloor \cdot \rfloor$ 表示向下取整运算。因此，如果你的测试数据 $X$ 包含的整数个数不超过 $T$ 个，则获得全部 $S$ 分。

评分

你必须将你的八个测试数据分别命名为 tasksauthor.outX.1，其中 $X$ 是子任务编号。在提交之前，你需要使用 gzip 压缩你的测试数据文件。在 Unix 系统中，以下命令可以生成压缩文件：

tar -cvzf tasksauthor.tgz tasksauthor.out*.1

在 Windows 系统中，请使用 7-Zip 或 Winzip 等软件来生成此 tar-gzipped 归档文件。仅提交 tasksauthor.tgz 文件到评测服务器。

评测服务器将解压该文件。对于每个子任务（设为子任务 $X$），评测机将执行以下步骤来确定该子任务应获得的奖励分数：

C1. 如果测试数据 tasksauthor.outX.1 不存在，则终止，不予评分。 C2. 检查 tasksauthor.outX.1 的格式。如果输入格式无效，则终止，不予评分。 C3. 以 tasksauthor.outX.1 作为输入运行代码 A。如果触发 TLE，则终止，不予评分。 C4. 以 tasksauthor.outX.1 作为输入运行代码 B。如果触发 TLE，则终止，并根据以下公式计算奖励分数： $\lfloor (S/100) \times \min(100 \times T/F, 100) \rfloor$

所有提供的代码都维护一个计数器（变量 counter），用于跟踪执行的操作次数。在代码执行过程中，当 counter 的值超过 1,000,000 时，我们认为该代码触发了 TLE。

单源最短路径 (SSSP)

给定一个带权有向图 $G$ 和两个顶点 $s$ 和 $t$，令 $p(s, t)$ 为从“源点” $s$ 到“终点” $t$ 的最短路径权重。如果 $t$ 不可从 $s$ 到达，则定义 $p(s, t) = 1,000,000,000$。在本题中，输入为图 $G$ 和一个包含 $Q$ 个查询的序列 $(s_1, t_1), (s_2, t_2), \dots, (s_Q, t_Q)$。输出为相应的查询结果 $p(s_1, t_1), p(s_2, t_2), \dots, p(s_Q, t_Q)$。

输入格式

输入文件由两部分组成。第一部分描述带权有向图 $G$ 的邻接表。第二部分描述 $G$ 上的最短路径查询。

第一部分以一行整数 $V$ 开头，表示 $G$ 中的顶点数。顶点编号为 $0, 1, \dots, V - 1$。随后有 $V$ 行，每一行对应一个顶点，从顶点 0 开始。每行以 $n_i$ 开头，表示顶点 $i$ 有多少条出边。接下来是 $n_i$ 对整数 $(j, w)$，每对对应一条出边。对中的第一个整数 $j$ 是边指向的顶点标签，第二个整数 $w$ 是边的权重。

第二部分以一行整数 $Q$ 开头。接下来有 $Q$ 行。第 $k$ 行包含两个整数 $s_k$ 和 $t_k$，分别对应源顶点和目标顶点。

同一行中任意两个连续的整数必须至少由一个空格分隔。此外，输入满足以下条件：

1. $0 < V \le 300$
2. $n_i$ 是非负整数，$\forall i \in [0..V - 1]$
3. $0 \le j < V$
4. $|w| < 10^6$，其中 $|w|$ 表示 $w$ 的绝对值
5. $0 \le \sum_{i=0}^{V-1} n_i \le 5000$
6. $0 < Q \le 10$
7. $0 \le s_k < V, 0 \le t_k < V, \forall k \in [1..Q]$
8. 图 $G$ 不得包含任何负权环

请注意，评测服务器将在步骤 C2 中检查上述约束。

输出文件格式在本任务中不太重要。输出由 $Q$ 行组成，第 $k$ 行包含整数 $p(s_k, t_k)$。为方便起见，提供的代码将在输出末尾打印变量 counter 的值。

Mystery 问题

给定一个具有 $V$ 个顶点和 $E$ 条边的无向输入图 $G$，为 $G$ 中的每个顶点标记一个整数 $\in [0..(X - 1)]$，使得 $G$ 中任意边的两个端点都没有相同的标签。对于图 $G$，$X$ 的值必须尽可能小。

输入格式

输入文件以一行两个整数 $V$ 和 $E$ 开头。随后有 $E$ 行。每行包含两个整数 $a$ 和 $b$，表示 $G$ 中的一条无向边 $(a, b)$。此外，输入满足以下约束（将在步骤 C2 中检查）：

1. $70 < V < 1000$
2. $1500 < E < 10^6$
3. 对于任意边 $(a, b)$，满足 $a \neq b, 0 \le a < V, 0 \le b < V$，且该边在 $G$ 中仅出现一次。

输出文件以一行整数 $X$ 开头，表示使得顶点标记可行的最小整数。下一行包含 $V$ 个整数，描述顶点 0, 1, ..., $V - 1$ 的整数标签，最后一行是 counter 的值。

附录：伪代码

以下是所提供代码的算法。变量 counter 通过跟踪某些操作来“近似”运行时间。我们的评测服务器使用这些实现代码的 C++ 版本。

FloydWarshall.cpp/pas

// pre-condition: the graph is stored in an adjacency matrix M
counter = 0
for k = 0 to V-1
for i = 0 to V-1
for j = 0 to V-1
increase counter by 1;
M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
for each query p(s,t)
output M[s][t];

OptimizedBellmanFord.cpp/pas

// pre-condition: the graph is stored in an adjacency list L
counter = 0
for each query p(s,t);
dist[s] = 0; // s is the source vertex
loop V-1 times
change = false;
for each edge (u,v) in L
increase counter by 1;
if dist[u] + weight(u,v) < dist[v]
dist[v] = dist[u] + weight(u,v);
change = true;
if change is false // this is the ’optimized’ Bellman Ford
break from the outermost loop;
output dist[t];

ModifiedDijkstra.cpp/pas

// pre-condition: the graph is stored in an adjacency list L
counter = 0;
for each query p(s,t)
dist[s] = 0;
pq.push(pair(0, s)); // pq is a priority queue
while pq is not empty
increase counter by 1;
(d, u) = the top element of pq;
remove the top element from pq;
if (d == dist[u])
for each edge (u,v) in L
if (dist[u] + weight(u,v) ) < dist[v]
dist[v] = dist[u] + weight(u,v);
insert pair (dist[v], v) into the pq;
output dist[t];

Gamble1.cpp/pas

Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 0; // will never get TLE

Gamble2.cpp/pas

Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 1000001; // force this to get TLE

RecursiveBacktracking.cpp/pas

This algorithm tries X from 2 to V one by one
and stops at the first valid X.

For each X, the backtracking routine label vertex 0 with 0,
then for each vertex u that has been assigned a label,
the backtracking routine tries to assign
the smallest possible label up to label X-1 to its neighbor v,
and backtracks if necessary.

// Please check RecursiveBacktracking.cpp/pas to see
// the exact lines where the iteration counter is increased by 1

Figure 1. Example of a graph for the SSSP problem