Nosaukums
Ceļa kartogrāfija (roadmap)
Laika limits
2.00s
Atmiņas limits
64.0 MB
Grūtība
56%

Definīcija

Ģeogrāfijas institūts sadarbībā ar kosmosa aģentūru veic jauna ceļa fotogrāfēšanu, lai tos atzīmētu kartē. Pašlaik ceļš jau ir atrodams vairākās bildēs un ir zināms, kuri ceļa intervāli tajās ir nofotogrāfēti. Tas nozīmē, ka zinātniekiem ir nepieciešams uzzināt, kuri segmenti vēl ir jāsafotogrāfē. Ceļš ir tains un zinātnieki to iesaka uztvērt kā vienas dimensijas koordinātu plakni.


Ievaddatu raksturojums

Ievaddatu pirmajā rindā tiek dots bilžu skaits 0 <= N <= 10^6 un ceļa garums 1 <= M <= 10^9. Katrā nākamajā no N rindām tiek dotas intervāla koordinātes ar vērtību mazāku par M (sāk skaitīt no 0). Intervāla 2. koordināte ir iekļauta intervālā.


Izvaddatu raksturojums

Izvaddatos jāizvada visi intervāli augošā secībā, kuri nav nofotogrāfēti. Katrā rindā ir jāizvada intervāla koordinātes.


Piezīmes

Tā kā intervāls ir nevis 2 dimensiju plaknē, bet uz 1 dimensijas līnijas, tad kkordinātes apzīmē punktu uz līnijas un ir tikai 1 skaitlis. Tādēļ intervālu var apzīmēt ar 2 koordinātēm jeb 2 skaitļiem.

Testi ir sadalīti trīs grupās:

  1. 40% testu 0 <= N <= 100 un 1 <= M <= 100.
  2. 80% testu 0<= N <= 1000 un 1<= M <= 1000.
  3. 100% testu 0<= N <= 10^6 un 1 <= M <= 10^9.

Paraugdati

Stdin
2 17
0 7
11 16
Stdout
8 10

Stdin
4 17
2 7
5 5
7 8
11 14
Stdout
0 1
9 10
15 16

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.