Tarix kursu
Sizə təsadüfi qaydada hər bir mühazirə üçün bir tarixi hadisə olmaqla, mühüm tarixi hadisələr haqqında bir sıra mühazirələr vermək tapşırılıb. Hər bir hadisə müəyyən bir zaman intervalı [a_i, b_i] ərzində baş verib. İki hadisənin bir-biri ilə əlaqəli olduğunu deyəcəyik, əgər onların intervalları ümumi bir nöqtəyə malikdirsə. Əlaqəli hadisələr üzrə mühazirələri bir-birinə yaxın planlaşdırmaq rahat olardı. Bundan əlavə, əlaqəsiz hadisələr üzrə mühazirələr onların xronoloji ardıcıllığında planlaşdırılmalıdır (əgər A hadisəsi onunla əlaqəsiz olan B hadisəsindən əvvəl baş veribsə, A üzrə mühazirə B üzrə mühazirədən əvvəl olmalıdır).
Elə ən kiçik tam k ≥ 0 və elə bir mühazirə ardıcıllığı tapın ki, hər hansı iki əlaqəli hadisə bir-birindən ən çox k mühazirə məsafəsində olsun (nömrələri i və j olan mühazirələr bir-birindən |i - j| məsafəsindədir).
Giriş verilənləri
Birinci sətir testlərin sayını t ehtiva edir. Hər bir testin strukturu aşağıdakı kimidir:
Birinci sətir n (1 ≤ n ≤ 50000) dəyərini ehtiva edir. Növbəti n sətirin hər biri iki tam ədəd a_i və b_i (-10^9 ≤ a_i ≤ b_i ≤ 10^9) ehtiva edir - i-ci intervalın ucları. İntervallar cüt-cüt fərqlidir.
Çıxış verilənləri
Testlərə cavabları onların ardıcıllığı ilə çıxarın. Hər bir testin birinci sətiri ən kiçik k dəyərini ehtiva edir. Növbəti n sətir elə intervallar siyahısını ehtiva edir ki, hər hansı iki əlaqəli hadisə bir-birindən ən çox k mühazirə məsafəsində olsun. Əlaqəsiz intervalları düzgün ardıcıllıqla yerləşdirməyi unutmayın!