겨울이 왔다

겨울이 왔고 거대한 장벽은 무너졌다. 밤의 왕과 그의 죽은 자들의 군대가 이제 북부를 지배한다. 그들은 윈터펠을 제외한 북부의 모든 곳을 공격했다. 윈터펠은 오래된 마법으로 죽은 자들의 군대와 화이트 워커로부터 보호받고 있다.

북부는 N개의 노드로 이루어진 방향 있는 뿌리 트리이다. 각 노드에는 1부터 N까지 서로 다른 번호가 붙어 있고, 노드들은 방향 간선으로 연결되어 있다. 각 간선은 한 방향으로만 지날 수 있는 도로이며, 도로마다 화이트 워커가 정확히 한 명씩 지키고 있다. 뿌리는 1번 노드이고, 뿌리에서 도로를 따라가면 다른 모든 노드에 도달할 수 있다.

윈터펠은 번호 v인 노드에 있다. v가 반드시 뿌리인 것은 아니다. 존 스노우와 윈터펠에 남은 생존자들은 밤의 왕이 번호가 L 이상 R 이하인 노드 중 어딘가에 있다는 소식을 들었다. 존은 밤의 왕을 죽이지 않으면 전쟁에서 이길 희망이 없다고 판단하고, 이 목숨을 건 임무를 직접 수행하기로 했다.

데너리스, 티리온, 데이비스 경이 그를 말렸지만 설득하지 못했다. 그러자 티리온이 주어진 v, L, R에 대해 다음 계획을 세웠다.

• 존과 조라 모몬트 경이 임무를 수행한다.
• 두 사람은 각각 v에서 도달할 수 있고 번호가 L 이상 R 이하인 노드를 하나씩 골라 그곳을 확인하러 간다. 같은 노드를 고를 수는 없지만, 누가 v 자신을 고르는 것은 괜찮다.
• 안전을 위해 v에서 선택한 노드까지 가는 두 경로는 어떤 도로도 공유해서는 안 된다.
• 임무의 성과를 높이기 위해, 각자 지나가는 도로를 지키는 화이트 워커를 하나씩 처치한다.

각 시나리오의 v, L, R에 대해, 처치하는 화이트 워커의 총합이 최대가 되도록 노드 쌍을 찾는다.

첫 줄에 테스트 케이스 수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스의 첫 줄에는 노드 수 N (1 ≤ N ≤ 20,000)과 시나리오 수 q (1 ≤ q ≤ 10^5)가 공백으로 구분되어 주어진다.

다음 줄에는 정수 N - 1개 p1, p2, ..., pN-1이 주어진다. 이는 노드 pi에서 노드 i + 1로 가는 도로가 있다는 뜻이다.

이어서 q개의 줄에 각각 정수 v, L, R (1 ≤ v, L, R ≤ N)이 공백으로 구분되어 주어지며, 시나리오 하나를 나타낸다. L ≤ R이다.

각 시나리오마다 계획을 만족하는 최적의 노드 쌍으로 처치할 수 있는 화이트 워커의 최대 총합을 한 줄에 출력한다. 계획을 만족하는 서로 다른 두 노드의 쌍을 찾을 수 없으면 -1을 출력한다.

첫 번째 시나리오에서는 한 명이 5번 노드로, 다른 한 명이 6번 노드로 간다. 각자 화이트 워커를 2명씩 처치하므로 합은 4이다.

두 번째 시나리오에서는 범위 안의 어느 노드에 가든 1번에서 2번으로 가는 도로를 지나야 하는데, 계획상 이 도로는 허용되지 않는다.

세 번째 시나리오에서는 한 명은 2번 노드에 머물고, 다른 한 명은 3번 노드로 간다.

네 번째 시나리오에서는 도로 방향이 반대이므로 2번 노드에서 1번 노드로 갈 수 없고, 두 사람이 모두 2번 노드를 고를 수도 없다.