To jest zadanie typu "output-only". Pamiętaj, że nadal musisz wysłać kod, który wypisuje wynik, a nie sam plik tekstowy.

Poprawne 3-kolorowanie grafu to przypisanie kolorów (liczb) ze zbioru $\{1, 2, 3\}$ każdemu z $n$ wierzchołków w taki sposób, aby dla każdej krawędzi $(a, b)$ grafu, wierzchołki $a$ i $b$ miały różne kolory. Istnieje co najwyżej $3^n$ takich kolorowań dla grafu o $n$ wierzchołkach.

Pracujesz w firmie, której celem jest zostanie specjalistą w tworzeniu grafów o zadanej liczbie 3-kolorowań. Pewnego dnia dowiadujesz się, że wieczorem otrzymasz zlecenie stworzenia grafu o dokładnie $6k$ 3-kolorowaniach. Nie znasz dokładnej wartości $k$, wiesz jedynie, że $1 \le k \le 500$.

Nie chcesz czekać na konkretną wartość $k$, aby zacząć tworzyć graf. Dlatego wcześniej budujesz graf o co najwyżej 19 wierzchołkach. Następnie, po poznaniu konkretnego $k$, możesz dodać do grafu co najwyżej 17 krawędzi, aby uzyskać wymagany graf o dokładnie $6k$ 3-kolorowaniach.

Czy potrafisz to zrobić?

Wejście

Brak danych wejściowych dla tego zadania.

Wyjście

Najpierw wypisz $n$ oraz $m$ ($1 \le n \le 19$, $1 \le m \le \frac{n(n-1)}{2}$) — liczbę wierzchołków i krawędzi grafu początkowego (tego zbudowanego wcześniej). Następnie wypisz $m$ linii w formacie $(u, v)$ — krawędzie grafu.

Następnie, dla każdego $k$ od 1 do 500 wykonaj następujące czynności:

Wypisz $e$ — liczbę krawędzi, które dodasz dla tego konkretnego $k$ ($1 \le e \le 17$). Następnie wypisz $e$ linii w formacie $(u, v)$ — krawędzie, które dodasz do swojego grafu.

Graf nie może zawierać pętli własnych, a dla każdego $k$, wszystkie $m + e$ użytych krawędzi muszą być parami różne. Liczba 3-kolorowań grafu dla danego $k$ musi wynosić dokładnie $6k$.

Przykład

Wejście 1

-

Wyjście 1

3 2
1 2
2 3
1
1 3
0

Uwagi

Przykładowe wyjście zostało podane jako przykład. Zawiera ono wyjście dla $k = 1, 2$.