만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

꽃

시간 제한1초메모리 제한1024 MB

요약
뿌리가 있는 트리 모양으로 연결된 화분 N개와 각 화분의 물 요구량 A_i가 주어졌을 때, 두 사람이 최적으로 둘 때 먼저 시작하는 사람이 이기는지 판별합니다.
난이도

어려움10점 중 8점

유형
게임 이론, 트리, 동적 계획법
정답자
아직 제출이 없습니다

문제

호시는 11번부터 NN번까지 NN개의 벽걸이 화분을 다음과 같이 설치했다. 먼저 11번 화분을 가장 높은 곳에 걸었다. 그다음 22번부터 NN번까지 번호 순서대로 ii번 화분을 Pi<iP_i < i인 PiP_i번 화분보다 낮게 걸고, PiP_i번 화분에서 ii번 화분으로 위에서 아래로 흐르는 수도관을 연결했다.

화분을 모두 설치한 다음, 호시는 모든 화분에 꽃을 하나씩 심었다. ii번 화분의 꽃은 매일 AiA_i만큼의 물이 필요하며, APi≥AiA_{P_i} \ge A_i를 만족하도록 꽃을 심었다.

매일 모든 꽃에 정해진 양의 물을 주던 호시는 지루함을 느꼈다. 그래서 친구 유키와 함께 다음 게임을 하기로 했다.

호시부터 시작하여 호시와 유키가 번갈아 가며 다음 규칙으로 화분에 물을 준다.

  1. 11번 화분에 아직 A1A_1만큼의 물을 주지 않았다면 11번 화분을 고른다. 그렇지 않다면 2≤i≤N2 \le i \le N인 ii 중에서, PiP_i번 화분에는 이미 APiA_{P_i}만큼의 물을 주었고 ii번 화분에는 아직 AiA_i만큼의 물을 주지 않은 화분을 하나 고른다.
  2. ii번 화분에 연결된 수도관을 모두 닫고 ii번 화분에 총 물이 AiA_i가 될 때까지 물을 준다. 또는 ii번 화분을 포함해 ii번 화분에서 시작해 수도관을 통해 도달할 수 있는 모든 화분에 물을 11만큼 준다.

자신의 차례에 물을 줄 수 있는 화분이 없으면 그 사람이 게임에서 진다.

둘 다 이기기 위해 최선을 다한다고 할 때, 누가 이길지 구한다.

입력

첫 번째 줄에 테스트 케이스의 개수 TT가 주어진다. (1≤T≤1001\le T \le 100)

각 테스트 케이스는 세 개의 줄로 이루어진다. 첫 번째 줄에 벽걸이 화분의 개수 NN이 주어진다. (2≤N≤4002 \le N \le 400)

두 번째 줄에 P2,P3,…,PNP_2, P_3, \dots, P_N이 공백으로 구분되어 주어진다. (1≤Pi<i1 \le P_i < i)

세 번째 줄에 A1,A2,…,ANA_1, A_2, \dots, A_N이 공백으로 구분되어 주어진다. (1≤Ai≤1091 \le A_i \le 10^{9})

모든 테스트 케이스의 NN의 합은 400400을 넘지 않는다.

입력으로 주어지는 수는 모두 정수이다.

출력

각 테스트 케이스마다 호시가 이기면 First, 유키가 이기면 Second를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    2
    3
    1 1
    5 3 3
    2
    1
    2 1
    
    예상 출력
    First
    Second