Ravintolassa käy illan aikana n ryhmää. Tiedät, milloin kukin ryhmä tulee ravintolaan ja lähtee ravintolasta.

Jokainen ryhmä tarvitsee yhden pöydän ravintolasta, eikä samassa pöydässä voi istua samaan aikaan monta ryhmää. On kuitenkin sallittua, että samalla hetkellä yksi ryhmä lähtee pöydästä ja toinen ryhmä tulee samaan pöytään.

Tehtäväsi on selvittää, mikä on pienin määrä pöytiä, joka ravintolaan tarvitaan ryhmiä varten, ja miten ryhmät voi sijoittaa pöytiin.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: ryhmien määrä.

Tämän jälkeen syötteessä on n riviä, joista jokainen kuvaa yhden ryhmän. Rivillä on kaksi kokonaislukua a ja b: milloin ryhmä tulee ravintolaan ja lähtee ravintolasta.

Tuloste

Ohjelmasi tulee tulostaa ensin yksi kokonaisluku m: pienin pöytien määrä. Pöydät on numeroitu kokonaisluvuin 1,2,\ldots,m.

Tämän jälkeen ohjelmasi tulee ilmoittaa jokaiselle ryhmälle, mihin pöytään ryhmä sijoitetaan. Mikä tahansa oikea ratkaisu kelpaa.

Esimerkki

Syöte:

3
4 8
2 5
5 9

Tuloste:

2
1
2
2

Osatehtävä 1 (15 pistettä)

• 1 \le n \le 10
• 1 \le a < b \le 100

Osatehtävä 2 (41 pistettä)

• 1 \le n \le 1000
• 1 \le a < b \le 10^9

Osatehtävä 3 (44 pistettä)

• 1 \le n \le 10^5
• 1 \le a < b \le 10^9