Under construction

Still being built. Things may change

Flowers

Time limit1sMemory limit1024 MB

Summary
Given a rooted tree of N pots with water needs A_i, decide whether the first player wins the watering game when both players play optimally.
Level

Hard8 of 10

Topics
Game theory, Tree, Dynamic programming
Solved
No attempts yet

Problem

Hoshi installed NN wall-mounted flower pots numbered 11 to NN as follows. First, he hung pot 11 at the highest position. Then, for each ii from 22 to NN in order, he hung pot ii lower than pot PiP_i, where Pi<iP_i < i, and connected a water pipe that flows downward from pot PiP_i to pot ii.

After installing all the pots, Hoshi planted one flower in each pot. The flower in pot ii needs AiA_i units of water per day, and he planted the flowers so that APi≥AiA_{P_i} \ge A_i holds.

Hoshi got bored of watering the flowers the same amount every day. He decided to play the following game with his friend Yuki.

Hoshi starts, and Hoshi and Yuki take turns watering the pots under these rules.

  1. If pot 11 has not yet received A1A_1 units of water, choose pot 11. Otherwise, choose any pot ii with 2≤i≤N2 \le i \le N that has not yet received AiA_i units of water, where pot PiP_i has already received APiA_{P_i} units of water.
  2. Close all pipes connected to pot ii and water pot ii until its total water reaches AiA_i. Or, add 11 unit of water to pot ii and to every pot reachable from pot ii through the pipes, starting from pot ii.

If a player cannot water any pot on their turn, that player loses.

Assuming both players play optimally to win, determine who wins.

Input

The first line contains the number of test cases TT. (1≤T≤1001 \le T \le 100)

Each test case consists of three lines. The first line contains NN, the number of pots. (2≤N≤4002 \le N \le 400)

The second line contains P2,P3,…,PNP_2, P_3, \dots, P_N, separated by spaces. (1≤Pi<i1 \le P_i < i)

The third line contains A1,A2,…,ANA_1, A_2, \dots, A_N, separated by spaces. (1≤Ai≤1091 \le A_i \le 10^{9})

The sum of NN over all test cases does not exceed 400400.

All input values are integers.

Output

For each test case, print First if Hoshi wins, or Second if Yuki wins, on a separate line.

Examples1

  1. Example 1

    Input
    2
    3
    1 1
    5 3 3
    2
    1
    2 1
    
    Expected output
    First
    Second