Floyd sai

Valera đang nghiên cứu thuật toán Floyd để tính khoảng cách ngắn nhất giữa mọi cặp đỉnh của một đồ thị vô hướng, liên thông gồm $n$ đỉnh và $m$ cạnh (không có khuyên và không có cạnh bội).

Ngoài ra, Valera đánh dấu đúng $k$ đỉnh $a_1,a_2,\dots ,a_k$. Đoạn mã của Valera như sau:

ans[i][j] // khoang cach ngan nhat giua cap dinh i, j
a[i]      // cac dinh duoc Valera danh dau

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
        if (i == j) ans[i][j] = 0;
        else        ans[i][j] = INF;   // INF la mot so rat lon

for (i = 1; i <= m; i++) {
    doc mot cap dinh u, v co canh vo huong noi giua chung;
    ans[u][v] = 1;
    ans[v][u] = 1;
}

for (i = 1; i <= k; i++) {
    v = a[i];
    for (j = 1; j <= n; j++)
        for (r = 1; r <= n; r++)
            ans[j][r] = min(ans[j][r], ans[j][v] + ans[v][r]);
}

Điểm khác biệt so với Floyd đúng: vòng lặp cập nhật chỉ chạy qua các đỉnh đã được đánh dấu $a_1,\dots ,a_k$ làm đỉnh trung gian (Floyd đúng phải chạy qua tất cả $n$ đỉnh). Vì thế đoạn mã có thể tính sai.

Cho trước tập đỉnh được đánh dấu, hãy dựng một đồ thị vô hướng liên thông gồm đúng $n$ đỉnh và $m$ cạnh (không khuyên, không cạnh bội) sao cho đoạn mã của Valera tính sai khoảng cách ngắn nhất cho ít nhất một cặp đỉnh $(i,j)$. Nếu không tồn tại đồ thị như vậy, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• Dòng thứ hai chứa $k$ số nguyên phân biệt $a_1,a_2,\dots ,a_k$ là các đỉnh được đánh dấu.

Dữ liệu ra

• Nếu không tồn tại đồ thị thoả mãn, in ra $-1$.
• Ngược lại, in ra $m$ dòng, mỗi dòng gồm hai số nguyên $u$, $v$ mô tả một cạnh vô hướng của đồ thị. Đồ thị phải liên thông, không có khuyên và không có cạnh bội.

Nếu có nhiều đồ thị thoả mãn, in ra một đồ thị bất kỳ.

Ràng buộc

• $3\le n\le 300$
• $2\le k\le n$
• $n-1\le m\le {\displaystyle \frac{n(n-1)}{2}}$
• $1\le a_i\le n$, các $a_i$ đôi một phân biệt.

Ví dụ