问题 Q: Misha, Grisha and Underground
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：4
通过：2
题目描述
D. Misha, Grisha and Underground
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Misha and Grisha are funny boys, so they like to use new underground. The underground has n stations connected with n-1 routes so that each route connects two stations, and it is possible to reach every station from any other.
The boys decided to have fun and came up with a plan. Namely, in some day in the morning Misha will ride the underground from station s to station f by the shortest path, and will draw with aerosol an ugly text "Misha was here" on every station he will pass through (including s and f). After that on the same day at evening Grisha will ride from station t to station f by the shortest path and will count stations with Misha's text. After that at night the underground workers will wash the texts out, because the underground should be clean.
The boys have already chosen three stations a, b and c for each of several following days, one of them should be station s on that day, another should be station f, and the remaining should be station t. They became interested how they should choose these stations s, f, t so that the number Grisha will count is as large as possible. They asked you for help.
The boys decided to have fun and came up with a plan. Namely, in some day in the morning Misha will ride the underground from station s to station f by the shortest path, and will draw with aerosol an ugly text "Misha was here" on every station he will pass through (including s and f). After that on the same day at evening Grisha will ride from station t to station f by the shortest path and will count stations with Misha's text. After that at night the underground workers will wash the texts out, because the underground should be clean.
The boys have already chosen three stations a, b and c for each of several following days, one of them should be station s on that day, another should be station f, and the remaining should be station t. They became interested how they should choose these stations s, f, t so that the number Grisha will count is as large as possible. They asked you for help.
Input
The first line contains two integers n and q (2≤n≤105, 1≤q≤105)− the number of stations and the number of days. The second line contains n-1 integers p2,p3,...,pn (1≤pi≤n). The integer pi means that there is a route between stations pi and i. It is guaranteed that it's possible to reach every station from any other.
The next q lines contains three integers a, b and c each (1≤a,b,c≤n)− the ids of stations chosen by boys for some day. Note that some of these ids could be same.
Output
Print q lines. In the i-th of these lines print the maximum possible number Grisha can get counting when the stations s, t and f are chosen optimally from the three stations on the i-th day.
Examples
Input
3 2 1 1 1 2 3 2 3 3
Output
2 3
Input
4 1 1 2 3 1 2 3
Output
2
Note
In the first example on the first day if s = 1, f = 2, t = 3, Misha would go on the route 1 
2, and Grisha would go on the route 3 1 2. He would see the text at the stations 1 and 2. On the second day, if s = 3, f = 2, t = 3, both boys would go on the route 3 1 2. Grisha would see the text at 3 stations. In the second examle if s = 1, f = 3, t = 2, Misha would go on the route 1
2 3, and Grisha would go on the route 2 3 and would see the text at both stations.
米莎和格里莎是有趣的男孩，所以他们喜欢使用新的地下室。地下有n个车站与n-1条路线相连，因此每条路线连接两个车站，并且可以从任何其他车站到达每个车站。
男孩们决定玩得开心，并想出了一个计划。也就是说，在早上的某一天，米莎将乘坐地铁从s站到f站，走最短的路，并在他将要经过的每个车站（包括s和f）上用气溶胶画出一个丑陋的文字“米莎在这里”。之后的同一天晚上，Grisha将以最短的路径从t站骑到f站，并用Misha的文本计算站点。之后，在晚上，地下工作人员会把文本洗出来，因为地下应该是干净的。
男孩们已经为接下来的几天中的每一天选择了三个站a、b和c，其中一个站当天应该是站s，另一个站应该是站f，剩下的站应该是t。他们向你求助。
输入格式
第一行包含两个整数n和q（2≤n≤105，1≤q≤105）−站点数量和天数。
第二行包含n-1个整数p2，p3，。。。，pn（1≤pi≤n）。整数pi表示站点pi和i之间有一条路线。保证可以从任何其他站点到达每个站点。
接下来的q行包含三个整数a、b和c，每个整数（1≤a、b、c≤n）——男孩在某一天选择的车站ID。注意，其中一些id可能是相同的。
第二行包含n-1个整数p2，p3，。。。，pn（1≤pi≤n）。整数pi表示站点pi和i之间有一条路线。保证可以从任何其他站点到达每个站点。
接下来的q行包含三个整数a、b和c，每个整数（1≤a、b、c≤n）——男孩在某一天选择的车站ID。注意，其中一些id可能是相同的。
输出格式
打印q行。在这些行的第i行中，当在第i天从三个站点中最佳选择站点s、t和f时，Grisha可以得到的最大可能数量。
输入样例 复制
3 2
1 1
1 2 3
2 3 3输出样例 复制
2
3数据范围与提示
在第一天的第一个例子中，如果s＝1，f＝2，t＝3，米莎将走12号线，格里莎将走3号线。他会在第1站和第2站看到文本。第二天，如果s=3，f=2，t=3，两个男孩都会走3 1 2路。Grisha将在3个站点看到文本。
在第二个例子中，如果s=1，f=3，t=2，米莎将走1 2 3路线，而格里莎将走2 3路线并在两个车站看到文本。
在第二个例子中，如果s=1，f=3，t=2，米莎将走1 2 3路线，而格里莎将走2 3路线并在两个车站看到文本。