Masala #0457

Xotira 16 MB Vaqt 1000 ms
14

SPACE-X

Space-X kompaniyasining asoschisi Elon Musk yangi loyihaga qo’l urmoqda. Ushbu loyihaga ko’ra 2022-yil mobaynida Space-X kompaniyasi Mars sayyorasiga 2 ta astronavtlarni uchurmoqchi. Ushbu loyiha global miqyosdagi loyiha bo’lgani uchun juftlikdagi astronavtlar turli millatlarga mansub bo’lishi maqsadga muvofiq. Sizga astronavtlarning Glob-ID identifikatsiya raqamlari juftliklar ro’yxati beriladi. Har bir juftlik bir millatga mansub kishilar hisoblanadi. Sizning vazifangiz SPACE-X kompaniyasiga turli mamlakatlardan qancha kosmonavtlar juftligini marsga yuborish uchun tanlash mumkinligini aniqlovchi dastur tuzib berish kerak. Agar ushbu dasturni muvaffaqiyatli tuza olsangiz Space-X ga ishga kirish uchun birinchi qadamni bosgan bo’lasiz.

Namuna:

\(n=4\) astronavtlar soni

Ularning Glob-ID lari [0,1,2,3] ko’rinishda tartiblangan.

astronavtlar = [1,2], [2,3]  juftliklar berilsa bu yerda: 0 boshqa millat va [1,2,3] esa boshqa millat vakillari. Marsga yuborish uchun 3 ta juftlik to’g’ri keladi: [0,1], [0,2] va [0,3].


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita \(n \space (1 \le n \le10^5)\) va \(p \space (1 \le p \le10^4)\) butun sonlar, astronavtlar soni va juftliklar son iberiladi. Keyingi \(p\) qatorning har birida bir xil millatga mansub ikki astronavtning Glob-ID larini bildiruvchi bo'shliq bilan ajratilgan 2 ta butun son beriladi.

 


Chiquvchi ma'lumotlar:

Bitta butun son, marsga uchirish mumkin bo’lgan juftliklar soni.


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