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