Порядок Штралера
У геології річкову систему можна зобразити як орієнтований граф. Кожен відрізок річки представлений ребром, причому напрямок ребра відповідає напрямку течії річки. Вершинами є витоки річок (наприклад, озеро або струмок), місця злиття або розгалуження річок, а також гирла річок.
Порядок Штралера річкової системи визначається наступним чином:
порядок вершини-витоку дорівнює 1.
для кожної іншої вершини нехай i - найбільший порядок серед усіх вузлів, що знаходяться вгору за течією. Якщо лише один з таких вузлів має порядок i, тоді поточна вершина також має порядок i. Якщо два або більше вузлів вгору за течією мають порядок i, то порядок поточної вершини дорівнює i + 1.
Порядок всієї річкової системи дорівнює порядку вершини-гирла. У наведеному прикладі річкова система має лише одне гирло. Порядок Штралера дорівнює трьом (3).
Число в прямокутнику - порядок Штралера. Число в колі - номер вершини.
Напишіть програму, яка визначить порядок заданої річкової системи.
Реальна річка з найбільшим порядком - Амазонка, її порядок дорівнює 12. Річка з найбільшим порядком у США - Міссісіпі, її порядок 10.
Вхідні дані
Перший рядок містить кількість тестів t (1 ≤ t ≤ 1000). Кожен тест слід обробити незалежно від інших.
Кожен тест складається з кількох рядків. Перший рядок кожного тесту містить три натуральних числа k, m і p (2 ≤ m ≤ 1000). k - номер тесту. m - кількість вершин у графі, p - кількість ребер. Далі слідують p рядків, кожен з яких задає ребро графа. Рядок містить два натуральних числа a і b, що вказують, що вода тече від a до b (1 ≤ a, b ≤ m). Вершина m - гирло річки, у неї немає вихідних ребер.
Вихідні дані
Для кожного тесту виведіть один рядок. У ньому вкажіть номер тесту, пробіл і порядок річкової системи.