402652: GYM100834 A Polycarp and Digits

Polycarp decided to get into the maze. The maze consists of N rooms connected by N - 1 corridors. In the beginning he is in the room 1, from which he can go to any other. While being in one of the rooms he tries to go to the one where he hasn't been yet. If there are no such rooms, Polycarp goes to the room where he came from or exits from the maze if he is in the room 1 and visited all other rooms. In each room there is an integer. Polycarp defined that in the room i recorded the number a_i, repeated b_i times. For example, if a_i equal to 123 and b_i equal to 3, the number will look like 123123123. Every time visiting another room, Polycarp writes the number specified number of times to his notepad. Besides it is considered that in the beginning Polycarp visits room 1. Therefore, he gets one more integer c, composed from all written numbers to the notepad. Polycarp is interested in all subsequences of the consecutive identical digits. Among these subsequences he chooses those who have the greatest length, and among the he chooses the one that is composed of the least digit. He needs to determine from what minimum digit and maximum length it is possible to construct such a subsequence.

The first line contains integer N — the number of rooms. 1 ≤ N ≤ 100000. The following N lines contain pairs of integers separated by spaces: a_i and b_i. 1 ≤ a_i ≤ 100 000, 1 ≤ b_i ≤ 1000. In next N - 1 lines there are pairs of integers f_i и t_i — description of the corridors. Corridor i connects room f_i with room t_i. Polycarp checks the unvisited rooms in a sequence, written in the input file.

In the first line print two numbers — the minimal digit that appears sequentially more often in c, and how many times it occurs.

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