Специально для \(n\) сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно \(n\) парковочных мест, каждому сотруднику должно достаться свое место.
Для экономии мест парковка будет разбита на несколько <<рядов>>. Места в каждом ряду нумеруются от \(1\) (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.
Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу \(t^\mathrm{in}_i\), и время, в которое он уезжает на следующий день \(t^\mathrm{out}_i\). Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать
-
появления доступного парковочного места, когда он приезжает;
-
возможности выехать, когда он заканчивает работу.
Более формально, если сотрудникам \(i\) и \(j\) назначены места \(p_i\) и \(p_j\) в одном ряду, и \(p_i < p_j\), должно выполняться \(t^\mathrm{in}_i \le t^\mathrm{in}_j\) и \(t^\mathrm{out}_i \ge t^\mathrm{out}_j\).
Определите, какое минимальное число рядов понадобится, чтобы можно было распределить всех сотрудников по местам на парковке указанным образом, и найдите соответствующее распределение сотрудников по местам.
Формат входных данных
В первой строке ввода дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют описания наборов входных данных.
В первой строке описания набора входных данных дано единственное целое число \(n\) — количество сотрудников, которых необходимо разместить на парковке.
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).
В следующих \(n\) строках перечислены времена въезда и выезда для каждого сотрудника, в \(i\)-й строке через пробел \(t^\mathrm{in}_i\) и \(t^\mathrm{out}_i\) (\(1 \le t^\mathrm{in}_i, t^\mathrm{out}_i \le 10^9\)).
Формат выходных данных
Выведите ответ на задачу для каждого набора входных данных в том порядке, в котором они перечислены во вводе.
В первой строке выведите число \(k\) — минимальное необходимое количество рядов.
В \(i\)-й из следующих \(n\) строк выведите через пробел сначала номер ряда, а затем номер места в этом ряду, которое надо отдать \(i\)-му сотруднику. Ряды и места нумеруются с единицы.
Если существует несколько различных ответов, минимизирующих \(k\), выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 3
2 4
3
5 4
7 3
6 1
4
1 8
2 7
3 5
4 6
2
3 2
1 5
|
2
1 1
2 1
2
1 1
2 1
1 2
2
1 1
1 2
1 3
2 1
1
1 2
1 1
|