Ninja found a family tree with ‘N’ members labeled from 0 to ‘N’-1. These ‘N’ members are connected by ‘N’-1 edges in the form of an N-ary tree. Now, Ninja is excited to find the K’th ancestor of each of the members of the family. Can you help Ninja to find the Kth ancestor of each of the members? You are given an N-ary tree having ‘N’ vertices labeled from 0 to ‘N’-1 and an integer ‘K’. Your task is to find the Kth ancestor of each node. If the Kth ancestor doesn’t exist, print -1 corresponding to that. For Example: For K = 2 in the given tree, the 2nd ancestor for node 4 is 2, and the 2nd ancestor for node 1 does not exist. Example Input Format: The first line of the input contains an integer, 'T,’ denoting the number of test cases. The first line of each test case contains two integers, the ‘N’ denoting the number of members and the given value of ‘K’. Next, ‘N’-1 lines have two integers i,j, denoting an edge between vertex i and vertex j. Output Format: For each test case, print ‘N’ values where ith value represents the Kth ancestor of the ith member. Print the output of each test case in a separate line. Note: You do not need to print anything. It has already been taken care of. Just implement the given function. Constraints: 1 <= T <= 10 1 <= N <= 10^6. 1 <= K <=N. Time limit: 1 sec Sample Input 1: 2 5 2 0 1 1 2 1 3 1 4 6 2 0 1 1 4 1 2 1 5 2 3 Sample Output 1: -1 -1 0 0 0 -1 -1 0 1 0 0 Explanation of sample input 1: For the first test case, Example Kth ancestor of Node 0 does not exist. So, the answer corresponding to Node 0 is -1. Kth ancestor of Node 1 does not exist. So, the answer corresponding to Node 1 is -1. Kth ancestor of Node 2 is Node 0. So, the answer corresponding to node 2 is 0. Kth ancestor of Node 3 is Node 0. So, the answer corresponding to node 3 is 0. Kth ancestor of Node 4 is Node 0. So, the answer corresponding to node 4 is 0. Hence,the answer array will be [-1,-1,0,0,0]. For the second test case, Example Kth ancestor of Node 0 does not exist. So, the answer corresponding to Node 0 is -1. Kth ancestor of Node 1 does not exist. So, the answer corresponding to Node 1 is -1. Kth ancestor of Node 2 is Node 0. So, the answer corresponding to node 2 is 0. Kth ancestor of Node 3 is Node 1. So, the answer corresponding to node 3 is 1. Kth ancestor of Node 4 is Node 0. So, the answer corresponding to node 4 is 0. Kth ancestor of Node 5 is Node 0. So, the answer corresponding to node 5 is 0. Hence,the answer array will be [-1,-1,0,1,0,0]. Sample Input 2: 2 7 1 0 1 0 2 1 4 1 5 1 6 2 3 7 1 0 1 0 2 0 6 1 3 3 4 4 5 Sample Output 2: -1 0 0 2 1 1 1 -1 0 0 1 3 4 0

#include<bits/stdc++.h>
using namespace std;

void kthAncestor(int k, int n, int **tree, int *ans, int node){
	ans[node] = -1;
	int prev = node;
	for (int i = 0; i < k; ++i)
	{
		int cur = ans[prev];
		if (cur == -1)
		{
			return;
		}
		prev = cur;
	}
	ans[node] = prev;
}

int main()
{
	int t;
	cin >> t;
	while(t--){
		int n, k;
		cin >> n >> k;
		int** tree = new int*[n];
		for (int i = 0; i < n; ++i)
		{
			tree[i] = new int[n];
			for (int j = 0; j < n; ++j)
			{