eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

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

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

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

prb6389

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

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

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

Giriş verilənləri

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

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
1
1 7 8
1 3
2 3
6 4
3 4
3 5
6 7
5 7
4 7
Çıxış verilənləri #1
1 3
Mənbə 2013 ACM Greater New York Region, Октябрь 27, Задача C