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 ai, repeated bi times. For example, if ai equal to 123 and bi 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: ai and bi. 1 ≤ ai ≤ 100 000, 1 ≤ bi ≤ 1000. In next N - 1 lines there are pairs of integers fi и ti — description of the corridors. Corridor i connects room fi with room ti. 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.
## Input
The first line contains integer N — the number of rooms. 1 ≤ N ≤ 100000. The following N lines contain pairs of integers separated by spaces: ai and bi. 1 ≤ ai ≤ 100 000, 1 ≤ bi ≤ 1000. In next N - 1 lines there are pairs of integers fi и ti — description of the corridors. Corridor i connects room fi with room ti. Polycarp checks the unvisited rooms in a sequence, written in the input file.
## Output
In the first line print two numbers — the minimal digit that appears sequentially more often in c, and how many times it occurs.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of rooms.
For each room $ i \in \{1, \dots, N\} $, let $ a_i \in \mathbb{Z}^+ $ and $ b_i \in \mathbb{Z}^+ $ denote the integer and its repetition count, respectively.
Let $ s_i \in \Sigma^* $ be the string formed by repeating the decimal representation of $ a_i $ exactly $ b_i $ times.
Let $ T = (V, E) $ be a tree with $ V = \{1, \dots, N\} $ and $ |E| = N-1 $, rooted at node 1.
Let $ \pi $ be the DFS traversal order of $ T $ starting at node 1, visiting unvisited neighbors in the order they appear in the input.
Let $ c = s_{\pi(1)} \cdot s_{\pi(2)} \cdots s_{\pi(N)} \in \Sigma^* $ be the concatenated string of all room strings in traversal order.
**Constraints**
1. $ 1 \leq N \leq 100000 $
2. $ 1 \leq a_i \leq 100000 $, $ 1 \leq b_i \leq 1000 $ for all $ i \in \{1, \dots, N\} $
3. The graph $ T $ is a tree with edges $ (f_j, t_j) $ for $ j \in \{1, \dots, N-1\} $
**Objective**
Find the maximum length $ L $ of any maximal contiguous subsequence of identical digits in $ c $, and among all such subsequences achieving $ L $, find the minimal digit $ d \in \{0, \dots, 9\} $ that appears in such a subsequence.
Output: $ (d, L) $