#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<typename T, typename Compare>
class Kopiec //na podstawie hxxp://students.mimuw.edu.pl/~szreder/skrypt.pdf
{
T* dane;
int rozm;
int gora;
Compare comp;
void heapify_up(int id)
{
int rodzic = id / 2;
if (rodzic && comp(dane[id], dane[rodzic]))
{
swap(dane[rodzic], dane[id]);
heapify_up(rodzic);
}
}
void heapify_down(int id)
{
int lewy = id * 2, prawy = lewy + 1;
int zmien = id;
if (lewy <= gora && comp(dane[lewy], dane[zmien]))
{
zmien = lewy;
}
if (prawy <= gora && comp(dane[prawy], dane[zmien]))
{
zmien = prawy;
}
if (zmien != id)
{
swap(dane[zmien], dane[id]);
heapify_down(zmien);
}
}
void alokuj(int nowy_rozmiar)
{
T* nowe_dane = new T[nowy_rozmiar + 1];
for (int i = 1; i <= gora; ++i)
{
nowe_dane[i] = dane[i];
}
delete[] dane;
dane = nowe_dane;
rozm = nowy_rozmiar;
}
public:
Kopiec() : dane(new T[2]), rozm(2), gora(0) {}
~Kopiec() {delete[] dane;}
void reserve(int i) {alokuj(i + 1);}
T top()
{
return dane[1];
}
void insert(const T& t)
{
++gora;
if (gora >= rozm)
{
alokuj(rozm * 2);
}
dane[gora] = t;
heapify_up(gora);
}
void erase()
{
dane[1] = dane[gora--];
heapify_down(1);
}
void wypisz()
{
for (int i = 1; i <= gora; ++i)
{
cout << dane[i] << ' ';
}
cout << '\n';
}
void wczytaj(int ile)
{
alokuj(2 * ile);
gora = ile;
for (int i = 1; i <= ile; ++i)
{
cin >> dane[i];
}
for (int i = ile / 2; i >= 1; --i)
{
heapify_down(i);
}
}
bool empty()
{
return gora == 0;
}
};
struct Spotkanie
{
int start, end;
int id;
};
struct Przydzial
{
int id_sali;
int koniec_obecnego_spotkania;
};
int main()
{
ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int ile_sal, ile_spotkan;
cin >> ile_sal >> ile_spotkan;
vector<Spotkanie> spotkania(ile_spotkan);
char dummy;
int temp;
for (int i = 0; i < ile_spotkan; ++i)
{
cin >> temp >> dummy;
spotkania[i].start = 60 * temp;
cin >> temp;
spotkania[i].start += temp;
cin >> temp >> dummy;
spotkania[i].end = 60 * temp;
cin >> temp;
spotkania[i].end += temp;
spotkania[i].id = i + 1;
}
vector<vector<int>> sale(ile_spotkan);
sort(spotkania.begin(), spotkania.end(), [](const Spotkanie& a, const Spotkanie& b)->bool
{
if (a.start != b.start)
{
return a.start < b.start;
}
return a.end < b.end;
});
struct comp
{
bool operator()(const Przydzial& a, const Przydzial& b)
{
return a.koniec_obecnego_spotkania < b.koniec_obecnego_spotkania;
};
};
int licznik_sal = 0;
Kopiec<Przydzial, comp> kopiec;
for (const auto& s: spotkania)
{
if (kopiec.empty())
{
kopiec.insert(Przydzial{licznik_sal, s.end});
sale[licznik_sal++].push_back(s.id);
}
else
{
auto k = kopiec.top();
if (k.koniec_obecnego_spotkania <= s.start)
{
sale[k.id_sali].push_back(s.id);
kopiec.erase();
kopiec.insert(Przydzial{k.id_sali, s.end});
}
else// if (licznik_sal < sale.size())
{
sale[licznik_sal].push_back(s.id);
kopiec.insert(Przydzial{licznik_sal++, s.end});
}
}
}
int odbedzie_sie = 0;
sort(sale.begin(), sale.end(), [](const auto& a, const auto& b)->bool {return a.size() > b.size();});
for (int i = 0; i < min(ile_sal, ile_spotkan); ++i)
{
odbedzie_sie += sale[i].size();
}
cout << odbedzie_sie << '\n';
for (int i = 0; i < min(ile_sal, ile_spotkan); ++i)
{
if (sale[i].empty())
{
break;
}
for (int j: sale[i])
{
cout << j << ' ';
}
cout << '\n';
}
cout << '\n';
}
}