← 返回题目列表

Codeforces · 350/E

E. 错误的弗洛伊德

中文机器翻译题面 查看原题

Valera 使用搜索最短路径的算法进行实验。他最近研究了弗洛伊德算法,所以是时候使用它了。

Valera 已经编写了代码,用于计算由 n 个顶点和 m 个边组成的无向连通图中任意一对顶点之间的最短距离,不包含循环和多条边。此外,瓦莱拉决定标记部分顶点。他准确地标记了 k 个顶点 a1, a2, ..., ak。

Valera 的代码如下。

Valera 发现他的代码是错误的。帮助男孩。给定一组标记的顶点 a1, a2, ..., ak,找到这样的非有向连通图,由 n 个顶点和 m 个边组成,Valera 的代码计算出至少一对顶点 (i, j) 的错误最短距离。 Valera 非常渴望得到一个没有任何循环和多条边的图。如果不存在这样的图,则打印 -1。

输入

输入的第一行包含三个整数 n、m、k (3 ≤ n ≤ 300, 2 ≤ k ≤ n , $$n-1 \leq m \leq \frac{n(n-1)}{2}$$) — 顶点数、边数和标记顶点数。

输入的第二行包含 k 个空格分隔的整数 a1, a2, ... ak (1 ≤ ai ≤ n) — 标记顶点的数量。保证所有数字 ai 都是不同的。

输出

如果图表不存在,则在单行上打印 -1。否则,打印 m 行,每行包含两个整数 u、v — Valera 一直在寻找的图的边的描述。

示例

输入 #1

3 2 2
1 2

输出 #1

1 3
2 3

输入 #2

3 3 2
1 2

输出 #2

-1