Masala #1181

Xotira 64 MB Vaqt 1000 ms
14

Sayyohlar

Robolandiyada M ta ketma-ket bog' mavjud va ular 1 dan M gacha raqamlangan. Bugun Robolandiyaga N ta sayyoh tashrif buyurgan va \(i-\)sayyoh \([A_i:B_i]\) oraliqdagi barcha bog'larni aylanib chiqadi. Agar ikki sayyoh bitta bog'da uchrashib qolishsa, ular do'stlashadi.

Har bir sayyoh uchun kun oxirida do'stlashishi mumkin bo'lgan sayyohlarning maksimal sonini aniqlang.


Kiruvchi ma'lumotlar:

Kirish faylining 1-qatorida ikkita natural son - N va M \((1 \le N \le 2*10^5, 1 \le M \le 10^9)\) kiritiladi.

Keyingi N ta qatorning har birida ikkitadan butun son \(A_i\) va \(B_i \ (1 \le A \le B \le M)\) kiritiladi.


Chiquvchi ma'lumotlar:

Har bir sayyoh uchun alohida qatorda kun oxirida do'stlashishi mumkin bo'lgan sayyohlarning maksimal sonini chop eting.


Misollar
# input.txt output.txt
1
4 5
2 3
1 2
3 4
5 5
2
1
1
0