hotel

Într-un hotel există $n$ angajaţi în Departamentul Administrativ. Patronul hotelului hotărăşte să schimbe costumele personalului din acest departament astfel încât angajaţii care lucrează la etaje diferite să fie îmbrăcaţi în haine colorate diferit, iar cei care lucrează la acelaşi etaj să fie îmbrăcaţi în haine colorate la fel. Angajaţii au fiecare un cod unic dat printr-un număr natural format din maxim $4$ cifre.

Cerinţă

Să se determine o modalitate de alegere a culorilor costumelor care să respecte condiţiile de mai sus, precum şi numărul de modalităţi.

Date de intrare

Fişierul de intrare hotel.in are următoarea structură:

• pe prima linie se află două numere naturale, $n$ şi $k$ separate printr-un spaţiu ($k$ este numărul de culori).
• pe următoarele $n$ linii se află câte două numere naturale separate printr-un spaţiu, primul fiind codul, iar al doilea etajul asociat angajatului.

Date de ieșire

Prima linie a fişierului de ieşire hotel.out va conţine numărul de modalităţi. Ştiind că o culoare este codificată printr-un număr natural nenul mai mic sau egal cu $k$, în fişier se va scrie pe câte o linie (începând cu a doua) codul unei persoane şi culoarea costumului, valori separate prin câte un spaţiu. Ordinea de scriere în fişierul de ieşire va fi aceeaşi cu cea din fişierul de intrare.

Restricții și precizări

• $1 \leq n \leq 1 \ 000$
• Numărul de etaje din hotel $\leq 200$
• $1 \leq k \leq 200$.
• Dacă există mai multe soluţii se va afişa una singură.
• Dacă nu există soluţii, în fişier se va scrie o singură linie care va conţine numărul $0$.
• Numărul de modalităţi şi modalitatea de alegere a culorii costumelor se punctează separat ($70\%$ din punctaj pentru numărul de modalităţi şi $30\%$ pentru alegerea corectă a culorilor costumelor)

Exemplul 1

hotel.in

4 5
123 2
35 1
430 2
13 0

hotel.out

60
123 1
35 2
430 1
13 3

Exemplul 2

hotel.in

5 2
12 1
13 0
14 1
10 2
11 0

hotel.out

0