Tarix kursu#6772
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 hadisəsi onunla əlaqəsiz olan hadisəsindən əvvəl baş veribsə, üzrə mühazirə üzrə mühazirədən əvvəl olmalıdır).
Elə ən kiçik tam k \geq 0 və elə bir mühazirə ardıcıllığı tapın ki, hər hansı iki əlaqəli hadisə bir-birindən ən çox mühazirə məsafəsində olsun (nömrələri və olan mühazirələr bir-birindən |i-j| məsafəsindədir).
Birinci sətir testlərin sayını ehtiva edir. Hər bir testin strukturu aşağıdakı kimidir:
Birinci sətir (1 \leq n \leq 50000) dəyərini ehtiva edir. Növbəti sətirin hər biri iki tam ədəd a_i və b_i (-10^9 \leq a_i \leq b_i \leq 10^9) ehtiva edir — -ci intervalın ucları. İntervallar cüt-cüt fərqlidir.
Testlərə cavabları onların ardıcıllığı ilə çıxarın. Hər bir testin birinci sətiri ən kiçik dəyərini ehtiva edir. Növbəti sətir elə intervallar siyahısını ehtiva edir ki, hər hansı iki əlaqəli hadisə bir-birindən ən çox mühazirə məsafəsində olsun. Əlaqəsiz intervalları düzgün ardıcıllıqla yerləşdirməyi unutmayın!
Nümunə 1