Fox Ciel is developing an artificial intelligence (AI) for a game. This game is described as a game tree T with n vertices. Each node in the game has an evaluation value which shows how good a situation is. This value is the same as maximum value of child nodesf values multiplied by -1. Values on leaf nodes are evaluated with Cielfs special function -- which is a bit heavy. So, she will use alpha-beta pruning for getting root nodefs evaluation value to decrease the number of leaf nodes to be calculated.
By the way, changing evaluation order of child nodes affects the number of calculation on the leaf nodes. Therefore, Ciel wants to know the minimum and maximum number of times to calculate in leaf nodes when she could evaluate child node in arbitrary order. She asked you to calculate minimum evaluation number of times and maximum evaluation number of times in leaf nodes.
Ciel uses following algotithm:
function negamax(node, α, β) if node is a terminal node return value of leaf node else foreach child of node val := -negamax(child, -β, -α) if val >= β return val if val > α α := val return α
[NOTE] negamax algorithm
Input follows following format:
n p_1 p_2 ... p_n k_1 t_{11} t_{12} ... t_{1k} : : k_n t_{n1} t_{n2} ... t_{nk}
The first line contains an integer n, which means the number of vertices in game tree T.
The second line contains n integers p_i, which means the evaluation value of vertex i.
Then, next n lines which contain the information of game tree T.
k_i is the number of child nodes of vertex i, and t_{ij} is the indices of the child node of vertex i.
Input follows following constraints:
Print the minimum evaluation number of times and the maximum evaluation number of times in leaf node.
Please separated by whitespace between minimum and maximum.
minimum maximum
3 0 1 1 2 2 3 0 0
2 2
8 0 0 100 100 0 -100 -100 -100 2 2 5 2 3 4 0 0 3 6 7 8 0 0 0
3 5
8 0 0 100 100 0 100 100 100 2 2 5 2 3 4 0 0 3 6 7 8 0 0 0
3 4
19 0 100 0 100 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 2 2 3 0 2 4 5 0 3 6 7 8 3 9 10 11 3 12 13 14 3 15 16 17 2 18 19 0 0 0 0 0 0 0 0 0 0
7 12