eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Порядок Штралера

Порядок Штралера

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

В геологии речная система может быть представлена в виде ориентированного графа. Каждый отрезок реки представляется ребром; направление ребра совпадает с направлением течения реки. Вершинами являются истоки рек (например озеро или ручей), места слияния или расхождения рек, либо устья рек.

Порядок Штралера речной системы вычисляется следующим образом.

  • порядок вершины - истока равен 1.

  • для каждой другой вершины пусть i - наибольший порядок среди всех узлов, находящихся вверх по течению. Если только один из таких узлов имеет порядок i, тогда текущая вершина также имеет порядок i. Если два или более узла вверх по течению имеют порядок i, то порядок текущей вершины равен i + 1.

Порядок всей речной системы равен порядку вершины - устья. В приведенном примере речная система имеет только одно устье. Порядок Штралера равен трем (3).

prb6389

Число в прямоугольнике - порядок Штралера. Число в круге - номер вершины.

Напишите программу, которая определит порядок заданной речной системы.

Реальная река с наибольшим порядком - Амазонка, ее порядок равен 12. Река с наибольшим порядком в США - Миссисипи, ее порядок 10.

Входные данные

Первая строка содержит количество тестов t (1t1000). Каждый тест следует обработать независимо от других.

Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит три натуральных числа k, m и p (2m1000). k - номер теста. m - количество вершин в графе, p - количество ребер. Далее следуют p строк, каждая из которых задает ребро графа. Строка содержит два натуральных числа a и b, указывающих что вода течет от a к b (1a, bm). Вершина m - устье реки, у нее нет исходящих ребер.

Выходные данные

Для каждого теста вывести одну строку. В ней вывести номер теста, пробел и порядок речной системы.

Пример

Входные данные #1
1
1 7 8
1 3
2 3
6 4
3 4
3 5
6 7
5 7
4 7
Выходные данные #1
1 3
Источник 2013 ACM Greater New York Region, Октябрь 27, Задача C