Поликарп решил залезть в лабиринт. Лабиринт представляет собой N комнат, соединенных N - 1 коридорами. В начальный момент он находится в комнате 1, из которой он может дойти до любой другой. Находясь в очередной комнате, Поликарп пытается перейти из неё в комнату, в которой он еще не был. Если таких комнат нет, Поликарп переходит в комнату, из которой он пришел, или выходит из лабиринта, если он находится в комнате 1 и посетил все остальные комнаты. В каждой комнате записано определенное число. Поликарп определил, что в комнате i записано число ai, повторенное bi раз. Например, если ai равно 123, а bi — 3, число будет выглядеть как 123123123. Каждый раз, посещая очередную комнату, Поликарп записывает себе это число указанное число раз в блокнот. При этом считается, что в начальный момент Поликарп посещает комнату 1. Таким образом, у него получается еще одно число c, составленное из всех выписанных чисел. Поликарпа интересует все подпоследовательности подряд идущих одинаковых цифр. Среди таких подпоследовательностей он выбирает те, у которых длина наибольшая, а среди них он выбирает ту, которая составлена из наименьшей цифры. Ему нужно определить, из какой минимальной цифры и максимальной длины можно составить такую подпоследовательность.
В первой строке находится целое число N — количество комнат. 1 ≤ N ≤ 100000. В следующих N строках находятся пары чисел, разделенных пробелами: ai и bi. 1 ≤ ai ≤ 100 000, 1 ≤ bi ≤ 1000. В следующих N - 1 строках находятся пары целых чисел fi и ti — описание коридоров. Коридор i связывает комнату fi c комнатой ti. Поликарп проверяет комнаты в порядке, указанном во входном файле.
В первой строке выведите два числа — минимальная цифра, которая встречается в c наибольшее число раз подряд и сколько раз подряд она встречается.
3
11211 1
11111 1
11111 1
1 2
1 3
1 9
3
3 1
3 3
3 7
1 2
1 3
3 13
