Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Jealous Nobita

By Ahasan_1999 · Limits 10s, 1.0 GB · Custom Checker

Shizuka and Dekisugi are playing with a binary tree rooted at 11. 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 TT (1T5)\left(1 \leq T \leq 5\right) , the number of test cases.

Each test case contains an integer NN (1N20)\left(1 \leq N \leq 20\right), the number of nodes of the binary tree.


If Nobita cannot draw a binary tree, print “NO\texttt{NO}” (without quotes). Otherwise, print “YES\texttt{YES}” (without quotes) in a single line and in next N1N-1 lines print two integers u,vu,v (1u,vN)\left(1 \leq u, v \leq N\right) denoting the bidirectional edges of the binary tree. If there are multiple solutions then print any of them.


1 2
1 3
3 4
3 5

Case 1:Case\ 1 : At first Shizuka removes the perfect binary tree rooted at 33. Then Dekisugi removes node 22. Finally Shizuka removes node 11 . Dekisugi has no moves left so he loses.

case 1

Case 2:Case\ 2 : There is only one possible construction of the binary tree having two nodes. Shizuka removes the perfect binary tree rooted at 22. Then Dekisugi removes the only remaining node 11. Shizuka has no move left so she loses.

case 2



96% Solution Ratio

ma5bahEarliest, 8M ago

Karnis_052Fastest, 0.0s

Sajjad_fc13Lightest, 0 B

Coder_fahimShortest, 193B


Login to submit


Let NNN is odd. If it’s a complete binary tree, Shizuka wins by deleting it at once. Else, Shizuka d...

Toph uses cookies. By continuing you agree to our Cookie Policy.