Special Tree

In Today’s class, Chef is here to teach students about Trees. Tree is a a connected graph of N nodes and N-1 edges.

After class, Chef gave them an assignment to complete. Assignment is as follows :-
Given a tree with single node (root), we need to find whether we can build a tree with exactly N leaf nodes by applying given queries.

Query 1 : Choose any i in between 2 to K and any leaf node say L in current Tree, attach i leaf nodes to L. (We can choose any particular i only once)

Query 2 : Choose an existing edge of Tree and cut the edge. Remove the entire sub-tree attached with that edge.
Students need to answer T independent test cases. Can you help them ?

• If K = 5, N = 6. One possible way to build a tree with N = 6 leaf nodes is :-
o Query 1:1 = 5, leaf node = root. Now, there are 6 nodes in tree and 5 leaf nodes.

o Query 1 : 1 = 2, choose any of the 5 leaf nodes. Now, there are 8 nodes in tree an leaf nodes.
• If K = 2, N = 3. It is not possible to build tree with 3 leaf nodes using given queries.
Function Description

•K: Represents the maximum value of i allowed in Query 1.
•N: Represents the required number of leaf nodes.

Input Format :-

  1. First line contain an integer T (1<=T <= 105)​
  2. T line consist of two space separated integers K and N

Output Format:
Print 1 if chef can build tree having N-leaf nodes by following queries, otherwise print 0.

2 3
7 5


1 Like