A Fibonacci tree is a binary tree defined recursively for an integer n:

• An order $1$ Fibonacci tree consists of a single root node.

• An order $2$ Fibonacci tree consists of a root node with a left child that is an order $1$ Fibonacci tree.

• An order n Fibonacci tree ($n \geq 3$) consists of a root node with a left child that is an order $n - 2$ Fibonacci tree and a right child that is an order $n - 1$ Fibonacci tree.

Alice and Bob play a game on an order n Fibonacci tree. Alice moves first, and players take turns. In each turn, a player selects any remaining node and removes that node along with its entire subtree. The player who removes the root node loses the game.

Assuming both players play optimally, return true if Alice wins the game, or false if Bob wins.

Constraints:

• $1 \leq$ n $\leq 100$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.