Muallif: __thecrash__ 9ac2fe4079be

L. Signal tarmog'i

Vaqt limiti: 1500 ms Xotira limiti: 256 mb

Kosmik aloqa markazi \(n\) xil signal turini qo'llab-quvvatlaydi, ular \(1\) dan \(n\) gacha raqamlangan. \(i\)-turdagi signal uchun ruxsat etilgan chastota oralig'i \([a_i, b_i]\) berilgan.

Tarmoq deb \(T = (V, E)\) ildizli daraxtga aytiladi, unda har bir bog'lanish (qirra) yuqoridagi \(n\) turdan biriga tegishli. Tarmoq barqaror deyiladi, agar quyidagi ikki shart bajarilsa:

• Ixtiyoriy uchta \(X, Y, Z \in V\) tugun uchun, agar \((X, Y)\) va \((Y, Z)\) bog'lanishlari ikkalasi ham mavjud bo'lsa, ularning turlari har xil bo'lishi shart. (Boshqacha aytganda: bitta tugunga ulangan barcha bog'lanishlar — u yuqoriga ham, pastga ham bo'lsin — juft-jufti bilan turlari bo'yicha farqlanishi kerak.)
• Har bir signal turi \(i \in [1, n]\) uchun \(g(X, i)\) orqali \(X\) tugunidan markaz (ildiz)gacha bo'lgan yo'ldagi \(i\)-turdagi bog'lanishlar sonini belgilaymiz. U holda \(\max_{X \in V}\) \(g(X, i)\) qiymati \([a_i, b_i]\) oralig'ida yotishi shart.

Ikkita tarmoq \(T = (V, E)\) va \(T' = (V', E')\) bir xil tuzilishga ega (isomorf) deyiladi, agar:

• \(\vert{}V\vert{} = \vert{}V'\vert{}\);
• shunday biyeksiya \(f : V \to V'\) mavjudki: \(r\) va \(r'\) mos ravishda \(T\) va \(T'\)ning markazlari bo'lsa, \(f(r) = r'\); va har qanday \((X, Y) \in E\) uchun \((f(X), f(Y)) \in E'\) bo'lib, bu bog'lanishning turi \((f(X), f(Y))\) bog'lanishining turi bilan bir xil.

Sizga topshiriq — juft-jufti bilan izomorf bo'lmagan barqaror tarmoqlardan iloji boricha ko'prog'ini tanlash, va ularning maksimal sonini 2 moduli bo'yicha chiqarish.

Kiruvchi ma'lumotlar

Birinchi qatorda \(t\) (\(1 \le t \le 10^4\)) — test holatlari soni. Har bir test holati uchun: birinchi qatorda \(n\) (\(1 \le n \le 2 \times 10^6\)) — signal turlari soni; keyingi \(n\) qatorning har birida ikkita butun son \(a_i, b_i\) (\(0 \le a_i \le b_i \le 2 \times 10^5\), \(b_i \ge 1\)).

Kafolatlanadiki, barcha test holatlari bo'yicha \(n\) larning yig'indisi \(2 \times 10^6\) dan oshmaydi. \(m = \max_i b_i\) bo'lsin — barcha test holatlari bo'yicha \(m\) larning yig'indisi \(2 \times 10^5\) dan oshmaydi.

Chiquvchi ma'lumotlar

Har bir test holati uchun — tanlash mumkin bo'lgan maksimal tarmoqlar sonini \(2\) moduli bo'yicha (\(0\) yoki \(1\)) chop eting.

Misollar

1

3
2
0 1
1 2
2
2 2
1 2
3
1 1
1 1
1 1

0
1
0