Hotelliin on tulossa lähiaikoina $n$ asiakasta, joista jokainen majoittuu yhdessä huoneessa.

Tiedät jokaisen asiakkaan tulo- ja lähtöpäivän. Kaksi asiakasta voi majoittua samassa huoneessa, kunhan ensimmäisen asiakkaan lähtöpäivä on aiemmin kuin toisen asiakkaan tulopäivä.

Mikä on pienin määrä huoneita, joka riittää kaikkien asiakkaiden majoittamiseen? Entä miten huoneet voi jakaa käytännössä?

Syöte

Syötteen ensimmäisellä rivillä on yksi kokonaisluku $n$: asiakkaiden määrä.

Sitten syötteessä on $n$ riviä, joista jokainen kuvaa yhden asiakkaan. Kullakin rivillä on kaksi kokonaislukua $a$ ja $b$: asiakkaan tulo- ja lähtöpäivä.

Tuloste

Tulosta ensin yksi kokonaisluku $k$: pienin tarvittavien huoneiden määrä.

Tulosta sitten rivi, jossa on jokaisen asiakkaan huoneen numero samassa järjestyksessä kuin syötteessä. Huoneet on numeroitu $1,2,\ldots,k$.

Rajat

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

Esimerkki

Syöte:

3
1 2
2 4
4 4

Tuloste:

2
1 2 1