#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll find_what(vector<ll> fir, vector<ll> sec) {
if (sec.size() == 1) {
return sec[0];
}
vector<ll> fs, ss;
for (ll i = 0; i < sec.size(); i++) {
if (i % 2 == 0) {
fs.push_back(sec[i]);
} else {
ss.push_back(sec[i]);
}
}
if (are_connected(fir, ss)) {
return find_what(fir, ss);
} else {
return find_what(fir, fs);
}
}
vector<ll> longest_trip(ll n, ll d) {
vector<ll> nw;
nw.push_back(0);
vector<vector<ll>> comps;
for (ll i = 1; i < n; i++) {
comps.push_back(vector<ll>(1, i));
}
while (comps.size() > 1) {
vector<ll> now(1, nw.back());
if (are_connected(now, comps.back())) {
ll x = find_what(now, comps.back());
nw.push_back(x);
for (auto i : comps.back()) {
if (i != x) {
nw.push_back(i);
}
}
comps.pop_back();
continue;
}
vector<ll> nc = comps.back();
comps.pop_back();
while (!comps.empty()) {
if (are_connected(now, comps.back())) {
ll x = find_what(now, comps.back());
nw.push_back(x);
for (auto i : comps.back()) {
if (i != x) {
nw.push_back(i);
}
}
comps.pop_back();
break;
}
for (auto i : comps.back()) {
nc.push_back(i);
}
comps.pop_back();
}
comps.insert(comps.begin(), nc);
}
vector<ll> now(1, comps[0][0]);
if (are_connected(now, nw)) {
vector<ll> now1(1, nw[0]);
if (are_connected(now, now1)) {
reverse(nw.begin(), nw.end());
for (auto i : comps[0]) {
nw.push_back(i);
}
return nw;
}
}
if (comps[0].size() > nw.size()) {
swap(nw, comps[0]);
}
return nw;
vector<ll> now(1, comps[0][0]);
if (are_connected(now, nw)) {
vector<ll> now1(1, nw[0]);
if (are_connected(now, now1)) {
reverse(nw.begin(), nw.end());
for (auto i : comps[0]) {
nw.push_back(i);
}
return nw;
}
now1[0] = nw.back();
if (are_connected(now, now1)) {
for (auto i : comps[0]) {
nw.push_back(i);
}
return nw;
}
ll x = find_what(now, nw);
vector<ll> ans;
while (nw.back() != x) {
ans.push_back(nw.back());
nw.pop_back();
}
for (auto i : nw) {
ans.push_back(i);
}
for (auto i : comps[0]) {
ans.push_back(i);
}
return ans;
}
if (are_connected(nw, comps[0])) {
ll x = find_what(nw, comps[0]);
ll y = find_what(vector<ll>(1, x), nw);
vector<ll> ans;
for (auto i : nw) {
if (i != y) {
ans.push_back(i);
}
}
ans.push_back(y);
ans.push_back(x);
for (auto i : comps[0]) {
if (i != x) {
ans.push_back(i);
}
}
return ans;
}
if (nw.size() < comps[0].size()) {
swap(nw, comps[0]);
}
return nw;
}
#ifdef LOCAL
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()
{
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();
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