Problem Statement

Sorry, problem statement was modified.(12:51 JST)

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 nodes’ values multiplied by -1. Values on leaf nodes are evaluated with Ciel’s special function -- which is a bit heavy. So, she will use alpha-beta pruning for getting root node’s 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.

Added pseudocode.(13:17 JST)
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

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:

• $2 \\leq n \\leq 100$

• $\-10,000 \\leq p_i \\leq 10,000$

• $0 \\leq k_i \\leq 5$

• $2 \\leq t_{ij} \\leq n$

• Index of root node is $1$.

• Evaluation value except leaf node is always $0$. This does not mean the evaluation values of non-leaf nodes are $0$. You have to calculate them if necessary.

• Leaf node sometimes have evaluation value of $0$.

• Game tree T is tree structure.

Output

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```

* * *

### Sample Input 1

```plain
3
0 1 1
2 2 3
0
0

Output for the Sample Input 1

2 2

Sample Input 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

Output for the Sample Input 2

3 5

Sample Input 3

8
0 0 100 100 0 100 100 100
2 2 5
2 3 4
0
0
3 6 7 8
0
0
0

Output for the Sample Input 3

3 4

Sample Input 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

Output for the Sample Input 4

7 12

Source Name

Summer Camp 2013