#include "longesttrip.h"

#include <cassert>
#include <cstdio>
#include <random>
#include <string>
#include <vector>
#include <algorithm>

int finde(int s, std::vector<int> a) {
	auto t = a;
	for(;t.size() > 1;) {
		std::vector<int> A, B;
		for(int i = 0;i < (int) t.size();++i) {
			(i & 1 ? A : B).push_back(t[i]);
		}
		if(are_connected({s}, A)) {
			t = A;
		} else {
			t = B;
		}
	}
	return t[0];
}
std::pair<int, int> finde(std::vector<int> a, std::vector<int> b) {
	if(a.size() == 1 && b.size() == 1) {
		return {a[0], b[0]};
	}
	if(a.size() < b.size()) {
		auto [x, y] = finde(b, a);
		return {y, x};
	}
	std::vector<int> A, B;
	for(int i = 0;i < (int) a.size();++i) {
		(i & 1 ? A : B).push_back(a[i]);
	}
	if(are_connected(A, b)) {
		return finde(A, b);
	} else {
		return finde(B, b);
	}
}
std::vector<int> path(std::vector<int> now, std::vector<int> a) {
	std::vector<int> cl;
	for(;a.size();) {
		if(cl.size()) {
			if(are_connected({now.back()}, cl)) {
				int t = finde(now.back(), cl);
				iter_swap(cl.begin(), find(cl.begin(), cl.end(), t));
				now.insert(now.end(), cl.begin(), cl.end());
				cl = {};
				continue;
			}
		}
		for(;a.size();) {
			int t = a.back(); a.pop_back();
			if(are_connected({now.back()}, {t})) {
				now.push_back(t);
				break;
			} else {
				cl.push_back(t);
			}
		}
	}
	if(cl.size() && are_connected({now.back()}, cl)) {
		int t = finde(now.back(), cl);
		iter_swap(cl.begin(), find(cl.begin(), cl.end(), t));
		now.insert(now.end(), cl.begin(), cl.end());
		return now;
	}
	a = cl;
	if(a.empty()) return now;
	if(now.size() == 1) return a;
	if(are_connected({now[0]}, {now.back()})) {
		if(are_connected(now, a)) {
			auto [x, y] = finde(now, a);
			rotate(now.begin(), find(now.begin(), now.end(), x), now.end());
			iter_swap(a.end() - 1, find(a.begin(), a.end(), y));
			a.insert(a.end(), now.begin(), now.end());
			return a;
		} else {
			return now.size() < a.size() ? a : now;
		}
	} else {
		reverse(now.begin(), now.end());
		now.insert(now.end(), a.begin(), a.end());
		return now;
	}
}
std::vector<int> longest_trip(int N, int D) {
	std::vector<int> a(N);
	std::vector<int> now = {0};
	for(int i = 0;i < N;++i) {
		a[i] = i;
	}
	a.erase(a.begin());
	static std::mt19937 gen(20040430);
	shuffle(a.begin(), a.end(), gen);
	return path(now, a);
}

#ifdef zqj
static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;

static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;

static inline void protocol_violation(std::string message)
{
	printf("Protocol Violation: %s\n", message.c_str());
	exit(0);
}

bool are_connected(std::vector<int> A, std::vector<int> B)
{
	++call_counter;
	++total_call_counter;
	if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
	{
		protocol_violation("too many calls");
	}

	int nA = A.size(), nB = B.size();
	landmark_counter += nA + nB;
	if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
	{
		protocol_violation("too many elements");
	}

	if (nA == 0 || nB == 0)
	{
		protocol_violation("invalid array");
	}
	for (int i = 0; i < nA; ++i)
	{
		if (A[i] < 0 || N <= A[i])
		{
			protocol_violation("invalid array");
		}
		if (present[A[i]])
		{
			protocol_violation("invalid array");
		}
		present[A[i]] = true;
	}
	for (int i = 0; i < nA; ++i)
	{
		present[A[i]] = false;
	}
	for (int i = 0; i < nB; ++i)
	{
		if (B[i] < 0 || N <= B[i])
		{
			protocol_violation("invalid array");
		}
		if (present[B[i]])
		{
			protocol_violation("invalid array");
		}
		present[B[i]] = true;
	}
	for (int i = 0; i < nB; ++i)
	{
		present[B[i]] = false;
	}

	for (int i = 0; i < nA; ++i)
	{
		for (int j = 0; j < nB; ++j)
		{
			if (A[i] == B[j])
			{
				protocol_violation("non-disjoint arrays");
			}
		}
	}

	for (int i = 0; i < nA; ++i)
	{
		for (int j = 0; j < nB; ++j)
		{
			if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
			{
				return true;
			}
		}
	}

	return false;
}

int main()
{
	freopen("1.in", "r", stdin);
	assert(1 == scanf("%d", &C));
	int maximumCalls = 0;
	for (int c = 0; c < C; ++c)
	{
		call_counter = 0;
		assert(2 == scanf("%d %d", &N, &D));

		present.assign(N, false);
		U.resize(N);
		for (int i = 1; i < N; ++i)
		{
			U[i].resize(i);
			for (int j = 0; j < i; ++j)
			{
				assert(1 == scanf("%d", &U[i][j]));
			}
		}

		for (int i = 2; i < N; ++i)
		{
			for (int j = 1; j < i; ++j)
			{
				for (int k = 0; k < j; ++k)
				{
					if (U[i][j] + U[i][k] + U[j][k] < D)
					{
						printf("Insufficient Density\n");
						exit(0);
					}
				}
			}
		}

		std::vector<int> t = longest_trip(N, D);
		int l = t.size();
		for (int i = 1; i < l; ++i) {
			int a = t[i - 1];
			int b = t[i];
			if(U[std::max(a, b)][std::min(a, b)] == 0) {
				puts("error");
				exit(1);
			}
		}
		printf("%d\n", l);
		for (int i = 0; i < l; ++i)
		{
			printf(i == 0 ? "%d" : " %d", t[i]);
		}
		printf("\n");
		printf("%d\n", call_counter);

		maximumCalls = std::max(maximumCalls, call_counter);
		call_counter = 0;
	}
	printf("%d\n", maximumCalls);

	return 0;
}
#endif