Treść zadania

Na pewnej platformie społecznościowej znajduje się $n$ użytkowników. Mała S zebrała zbiór liczb $\{c_1, \dots, c_m\}$ o rozmiarze $m$. Na podstawie tych informacji, możliwą sieć obserwacji można przedstawić jako skierowany graf $G = (V, E)$, który spełnia następujące warunki:

• Zawiera $n$ użytkowników, czyli zbiór wierzchołków $V = \{1, 2, \dots, n\}$;
• Nie występują sytuacje, w których użytkownik obserwuje samego siebie lub wielokrotne obserwacje, czyli graf $G$ nie zawiera pętli własnych ani wielokrotnych krawędzi;
• Wszystkie relacje obserwacji są ściśle jednostronne, co oznacza, że dla dowolnej krawędzi skierowanej $(u, v) \in E$ zachodzi $(v, u) \notin E$;
• Dla każdego elementu $c_i$ ze zbioru ($1 \le i \le m$), w grafie $G$ istnieje co najmniej jeden wierzchołek, którego stopień wyjściowy (odpowiadający liczbie obserwowanych) lub stopień wejściowy (odpowiadający liczbie obserwujących) jest dokładnie równy $c_i$.

Musisz na podstawie informacji zebranych przez małą S odtworzyć sieć obserwacji o minimalnej łącznej liczbie obserwacji (czyli minimalnej liczbie krawędzi w grafie $G$).

Wejście

Pierwsza linia wejścia zawiera nieujemną liczbę całkowitą $o \in \{0, 1\}$, określającą parametr wyjściowy.

Druga linia wejścia zawiera dwie dodatnie liczby całkowite $n, m$ ($1 \le m < n \le 10^6$), oznaczające liczbę użytkowników oraz rozmiar zbioru zebranego przez małą S. Gwarantuje się, że jeśli $o = 0$, to $n \le 2 \times 10^3$.

Trzecia linia wejścia zawiera $m$ parami różnych dodatnich liczb całkowitych $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n - 1$), oznaczających elementy zbioru zebranego przez małą S.

Wyjście

Wypisz w pierwszej linii jedną dodatnią liczbę całkowitą $k$, oznaczającą minimalną łączną liczbę obserwacji we wszystkich możliwych sieciach obserwacji.

Jeśli $o = 0$, wypisz następnie $k$ linii, z których każda zawiera dwie dodatnie liczby całkowite $u, v$ ($1 \le u, v \le n$), oznaczające, że użytkownik $u$ obserwuje użytkownika $v$, czyli $(u, v) \in E$.

Przykład

Wejście 1

0
5 4
3 1 4 2

Wyjście 1

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