Shizuka and Dekisugi are playing with a binary tree rooted at . In each turn, the player chooses a subtree and erases it. The erased subtree must be a perfect binary tree. Shizuka takes the first turn. The player unable to move will lose the game.
Nobita wants to draw the initial binary tree for the game. Can Nobita draw the binary tree in such a way that Dekisugi will lose if both players play optimally?
Binary tree : A tree in which every node has at most two childs.
Perfect Binary tree : A binary tree in which all interior nodes have two children and all leaves have the same depth or same level. A single node is also a perfect binary tree.
Subtree : A subtree of a tree T is a tree consisting of a node in T and all of its descendants.
The first line contains an integer , the number of test cases.
Each test case contains an integer , the number of nodes of the binary tree.
If Nobita cannot draw a binary tree, print “” (without quotes). Otherwise, print “” (without quotes) in a single line and in next lines print two integers denoting the bidirectional edges of the binary tree. If there are multiple solutions then print any of them.
2 5 2
YES 1 2 1 3 3 4 3 5 NO
At first Shizuka removes the perfect binary tree rooted at . Then Dekisugi removes node . Finally Shizuka removes node . Dekisugi has no moves left so he loses.
There is only one possible construction of the binary tree having two nodes. Shizuka removes the perfect binary tree rooted at . Then Dekisugi removes the only remaining node . Shizuka has no move left so she loses.
Login to submit
Let NNN is odd. If it’s a complete binary tree, Shizuka wins by deleting it at once. Else, Shizuka d...