A tale of two trees

All submissions for this problem are available.
There are two trees; tree 1 has N_{1} nodes which are numbered from 1 to N_{1}, and tree 2 has N_{2} nodes which are numbered from 1 to N_{2}. Each tree is rooted at its node 1.
You should perform the following operation: choose an arbitrary node u in tree 2, remove the subtree of node u (the subtree formed by node u and all its direct or indirect descendants) from tree 2 and add the subtree to any leaf of tree 1 (ie. u should become a child of some leaf in tree 1). Note that u can also be the root of tree 2. Afterwards, discard the rest of tree 2 and keep only the modified tree 1. How many distinct trees can you obtain by performing this operation exactly once?
Note that tree 1 will remain rooted in its own node 1. Two trees are considered identical if you can reorder (without changing the root) the children in each node and renumber the nodes (except the root) to make them equal. (Intuitively, the structure of the trees must be same  we're dealing with rooted, unlabelled, unordered isomorphic trees.)
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two spaceseparated integers N_{1} and N_{2} denoting the number of nodes in tree 1 and tree 2 respectively.
The second line contains N_{1}  1 spaceseparated integers A_{2}, A_{3}, ..., A_{N1} with each A_{i} denoting the parent of node i in tree 1
The third line contains N_{2}  1 spaceseparated integers B_{2}, B_{3}, ..., B_{N2} with each B_{i} denoting the parent of node i in tree 2
Output
For each test case, output a single line containing the number of distinct trees obtained by performing the above operation exactly once.
Constraints
 1 ≤ T ≤ 10^{5}
 2 ≤ N_{1}, N_{2} ≤ 10^{5}
 The sum of N_{1} across all test cases does not exceed 10^{6}
 The sum of N_{2} across all test cases does not exceed 10^{6}
 1 ≤ A_{i}, B_{i} < i
Example
Input: 2 3 3 1 1 1 1 3 4 1 1 1 1 2 Output: 2 3
Explanation
Example case 1. There are two distinct trees that can be formed: the first type is making the entire tree 2 a child of one of the 2 leaves of tree 2 and the other being making one of the leaves of tree 2 a child of one of the leaves of tree 1. Note that which leaf doesn't matter as they can be rearranged to obtain the other way (i.e. if we add it to left leaf, then it is same as adding to the right leaf as we can rearrange the leafs to make it same)
Example case 2. The 3 distinct trees are formed by: make the entire tree 2, subtree rooted at node 2 or any of the leaf of tree 2 the child of a leaf of tree 1
Author:  balajiganapath 
Tags  balajiganapath 
Date Added:  30102017 
Time Limit:  1.2 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.5, PYPY 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 