Trên nền tảng mạng xã hội này, có tổng cộng $n$ người dùng. Tiểu S đã thu thập được một tập hợp các số có kích thước $m$ là $\{c_1, \dots, c_m\}$. Dựa trên thông tin này, một mạng lưới theo dõi khả thi có thể được trừu tượng hóa thành một đồ thị có hướng $G = (V, E)$ thỏa mãn các điều kiện sau:

• Bao gồm $n$ người dùng, tức là tập đỉnh $V = \{1, 2, \dots, n\}$;
• Không có trường hợp người dùng tự theo dõi chính mình hoặc theo dõi trùng lặp, tức là đồ thị $G$ không chứa khuyên và cạnh đa;
• Tất cả các mối quan hệ theo dõi đều là theo dõi một chiều nghiêm ngặt, nghĩa là với mọi cạnh có hướng $(u, v) \in E$, ta luôn có $(v, u) \notin E$;
• Với mỗi phần tử $c_i$ trong tập hợp ($1 \le i \le m$), trong đồ thị $G$ luôn tồn tại ít nhất một đỉnh có bậc ra (tương ứng với số người đang theo dõi) hoặc bậc vào (tương ứng với số người theo dõi mình) đúng bằng $c_i$.

Bạn cần dựa vào thông tin mà Tiểu S thu thập được để khôi phục lại một mạng lưới theo dõi có tổng số lượt theo dõi ít nhất (tức là đồ thị $G$ có số cạnh nhỏ nhất).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên không âm $o \in \{0, 1\}$, biểu thị tham số cho đầu ra.

Dòng thứ hai chứa hai số nguyên dương $n, m$ ($1 \le m < n \le 10^6$), biểu thị số lượng người dùng và kích thước tập hợp mà Tiểu S thu thập được. Đảm bảo rằng nếu $o = 0$, thì $n \le 2 \times 10^3$.

Dòng thứ ba chứa $m$ số nguyên dương đôi một khác nhau $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n - 1$), biểu thị các phần tử trong tập hợp mà Tiểu S thu thập được.

Dữ liệu ra

In ra một dòng chứa một số nguyên dương $k$, biểu thị giá trị nhỏ nhất của tổng số lượt theo dõi trong tất cả các mạng lưới theo dõi khả thi.

Nếu $o = 0$, sau đó in ra $k$ dòng, mỗi dòng chứa hai số nguyên dương $u, v$ ($1 \le u, v \le n$), biểu thị người dùng $u$ đã theo dõi người dùng $v$, tức là $(u, v) \in E$.

Ví dụ

Dữ liệu vào 1

0
5 4
3 1 4 2

Dữ liệu ra 1

7
3 2
4 1
3 4
4 5
3 5
4 2
3 1