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