| Codeforces Round 425 (Div. 2) |
|---|
| Закончено |
Миша и Гриша — веселые ребята, поэтому они любят кататься на новом метро. В метро есть n станций, соединенных n - 1 перегонами так, что каждый перегон соединяет две станции, и от каждой станции до любой другой можно добраться по перегонам.
Ребята решили повеселиться и затеяли кое-что. А именно, в какой-нибудь день утром Миша проезжает кратчайшим путем от станции s до станции f, и на каждой из станций, мимо которых он проехал (включая s и f), он рисует баллончиком корявую надпись «Здесь был Миша». После чего вечером того же дня, Гриша едет со станции t до станции f кратчайшим путем и считает количество станций, на которых обнаружит надпись Миши. После этого ночью этого же дня работники метро смывают все эти надписи, потому что метро должно быть чистым.
Ребята уже выбрали на несколько дней вперед по три станции a, b и c, одна из которых должна стать станцией s, другая — станцией f, а третья — станцией t в каждый из дней. Им стало интересно, как нужно выбрать из этих трех станций 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) — номера станций, которые выбрали ребята на очередной день. Обратите внимание, номера этих станций могут совпадать друг с другом.
Выведите q строк. В i-й строке выведите максимальное число, которое может насчитать Гриша при оптимальном выборе s, t и f из трех станций в i-й день.
3 2
1 1
1 2 3
2 3 3
2
3
4 1
1 2 3
1 2 3
2
В первом примере в первый день при s = 1, f = 2, t = 3, Миша поедет по маршруту 1 
2, а Гриша по маршруту 3 1 2. Он увидит надпись на станциях 1 и 2. Во второй день при s = 3, f = 2, t = 3, оба мальчика едут по маршруту 3 1 2. Гриша видит надпись на 3 станциях.
Во втором примере при s = 1, f = 3, t = 2, Миша поедет по маршруту 1 2 3, а Гриша по маршруту 2 3 и увидит надпись на обеих станциях.
