白雪公主¶

参考时限：2.5秒；内存限制：512 MiB. 目标平台按正式文件最慢中位数的两倍、向上取整到0.5秒校准，见评测环境.

背景故事¶

白雪公主请你帮她改造滑雪道。

这里的滑雪道连接着不同高度的地点，每条滑雪道只能沿指定方向通往同样高或更低的地点。你需要修建一些电梯，电梯也只能单向运行，但可以通往同样高或更高的地点。

白雪公主希望从任意地点出发，都能通过滑雪道和电梯到达其他所有地点。你要先让电梯的总提升高度尽可能小，再在此前提下尽量少修电梯。

有 \(n\) 个点和 \(m\) 条有向边，点 \(u\) 的高度为 \(h_u\) . 每条已有边 \(u\to v\) 均满足 \(h_u\ge h_v\) . 高度相等时，边仍只允许沿给定方向通行。已有边可以重复，也可以是自环。

你可以增加任意条有向边 \(s\to t\) ，但必须满足 \(s\ne t\) 且 \(h_s\le h_t\) . 每条新增边的代价是 \(h_t-h_s\) . 让最终的图强连通，即任意点都可以沿有向边到达任意其他点。

按以下优先级优化：先最小化新增边的总代价，再在最小总代价下最小化新增边数。输出任意最优方案；若不存在方案，输出 -1 .

下降链与连接两端的上行电梯

图中黑色边为已有滑雪道，蓝色边为新增电梯。总代价为 \(3-0=3\) ，只需一条新增边。

第一行两个整数 \(n,m\) . 第二行 \(n\) 个整数 \(h_1,\ldots,h_n\) . 接下来 \(m\) 行，每行两个整数 \(u,v\) ，表示已有边 \(u\to v\) .

无解时只输出一行 -1 . 否则第一行输出最小总代价，第二行输出该代价下的最少新增边数 \(k\) ，接下来 \(k\) 行各输出两个点 \(s,t\) ，表示新增边 \(s\to t\) . \(k=0\) 时不再输出边。

3
1
3 1

3 1
2 1 0
1 2

-1

7 3
4 5 1 0 5 4 4
5 1
7 1
7 4

\(1\le n\le500000\) , \(1\le m\le2000000\) , \(-10^9\le h_u\le10^9\) , \(1\le u,v\le n\) . 已有边满足 \(h_u\ge h_v\) .

由 Codex（GPT-6）补齐无解输出与自环、重边约定，记录为重新设计；点数、边数、高度范围和两级优化目标保持一致。

分值比例	额外条件
100%	无额外条件

共10个正式文件，每个10%。生成说明。