#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
struct Spotkanie
{
int start, end; //czasy przechowujemy w minutach
int id;
};
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;
list<Spotkanie> spotkania;
for (int i = 0; i < ile_spotkan; ++i)
{
int rg, rm, zg, zm;
char dummy;
cin >> rg >> dummy >> rm >> zg >> dummy >> zm;
spotkania.push_back(Spotkanie{rg * 60 + rm, zg * 60 + zm, i + 1});
}
spotkania.sort([](const Spotkanie& a, const Spotkanie& b)->bool
{
if (a.start != b.start)
{
return a.start < b.start;
}
return a.end > b.end;
});
vector<vector<int>> sale(ile_spotkan); //bedzie przechowywac poszczegolne sale, a one poszczegolne spotkania, ktore sie w nich odbeda
int odbedzie_sie = 0;
for (int i = 0; i < min(ile_sal, ile_spotkan); ++i) //zachlannie pakujemy spotkania do kazdej sali po kolei
{
int koniec_obecnego = -1;
if (spotkania.empty()) //jesli nie wykorzystamy wszystkich sal
{
break;
}
for (auto spotkanie = spotkania.begin(); spotkanie != spotkania.end();)
{
if (spotkanie->start >= koniec_obecnego) //jesli mozna wsadzic do obecnej sali jeszcze jedno spotkanie
{
koniec_obecnego = spotkanie->end;
sale[i].push_back(spotkanie->id);
spotkanie = spotkania.erase(spotkanie);
}
else
{
++spotkanie;
}
}
}
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';
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bGlzdD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgU3BvdGthbmllCnsKICAgIGludCBzdGFydCwgZW5kOyAvL2N6YXN5IHByemVjaG93dWplbXkgdyBtaW51dGFjaAogICAgaW50IGlkOwp9OwoKaW50IG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCS8vY2luLnRpZShudWxscHRyKTsKCiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUgKHQtLSkKICAgIHsKICAgICAgICBpbnQgaWxlX3NhbCwgaWxlX3Nwb3RrYW47CiAgICAgICAgY2luID4+IGlsZV9zYWwgPj4gaWxlX3Nwb3RrYW47CiAgICAgICAgbGlzdDxTcG90a2FuaWU+IHNwb3RrYW5pYTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBpbGVfc3BvdGthbjsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHJnLCBybSwgemcsIHptOwogICAgICAgICAgICBjaGFyIGR1bW15OwoKICAgICAgICAgICAgY2luID4+IHJnID4+IGR1bW15ID4+IHJtID4+IHpnID4+IGR1bW15ID4+IHptOwoKICAgICAgICAgICAgc3BvdGthbmlhLnB1c2hfYmFjayhTcG90a2FuaWV7cmcgKiA2MCArIHJtLCB6ZyAqIDYwICsgem0sIGkgKyAxfSk7CiAgICAgICAgfQoKICAgICAgICBzcG90a2FuaWEuc29ydChbXShjb25zdCBTcG90a2FuaWUmIGEsIGNvbnN0IFNwb3RrYW5pZSYgYiktPmJvb2wKICAgICAgICB7CiAgICAgICAgICAgIGlmIChhLnN0YXJ0ICE9IGIuc3RhcnQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJldHVybiBhLnN0YXJ0IDwgYi5zdGFydDsKICAgICAgICAgICAgfQogICAgICAgICAgICByZXR1cm4gYS5lbmQgPiBiLmVuZDsKICAgICAgICB9KTsKCiAgICAgICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBzYWxlKGlsZV9zcG90a2FuKTsgLy9iZWR6aWUgcHJ6ZWNob3d5d2FjIHBvc3pjemVnb2xuZSBzYWxlLCBhIG9uZSBwb3N6Y3plZ29sbmUgc3BvdGthbmlhLCBrdG9yZSBzaWUgdyBuaWNoIG9kYmVkYQogICAgICAgIGludCBvZGJlZHppZV9zaWUgPSAwOwoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG1pbihpbGVfc2FsLCBpbGVfc3BvdGthbik7ICsraSkgLy96YWNobGFubmllIHBha3VqZW15IHNwb3RrYW5pYSBkbyBrYXpkZWogc2FsaSBwbyBrb2xlaQogICAgICAgIHsKICAgICAgICAgICAgaW50IGtvbmllY19vYmVjbmVnbyA9IC0xOwogICAgICAgICAgICBpZiAoc3BvdGthbmlhLmVtcHR5KCkpIC8vamVzbGkgbmllIHd5a29yenlzdGFteSB3c3p5c3RraWNoIHNhbAogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgZm9yIChhdXRvIHNwb3RrYW5pZSA9IHNwb3RrYW5pYS5iZWdpbigpOyBzcG90a2FuaWUgIT0gc3BvdGthbmlhLmVuZCgpOykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKHNwb3RrYW5pZS0+c3RhcnQgPj0ga29uaWVjX29iZWNuZWdvKSAvL2plc2xpIG1vem5hIHdzYWR6aWMgZG8gb2JlY25laiBzYWxpIGplc3pjemUgamVkbm8gc3BvdGthbmllCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAga29uaWVjX29iZWNuZWdvID0gc3BvdGthbmllLT5lbmQ7CiAgICAgICAgICAgICAgICAgICAgc2FsZVtpXS5wdXNoX2JhY2soc3BvdGthbmllLT5pZCk7CiAgICAgICAgICAgICAgICAgICAgc3BvdGthbmllID0gc3BvdGthbmlhLmVyYXNlKHNwb3RrYW5pZSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgKytzcG90a2FuaWU7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHNvcnQoc2FsZS5iZWdpbigpLCBzYWxlLmVuZCgpLCBbXShjb25zdCBhdXRvJiBhLCBjb25zdCBhdXRvJiBiKS0+Ym9vbCB7cmV0dXJuIGEuc2l6ZSgpID4gYi5zaXplKCk7fSk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtaW4oaWxlX3NhbCwgaWxlX3Nwb3RrYW4pOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBvZGJlZHppZV9zaWUgKz0gc2FsZVtpXS5zaXplKCk7CiAgICAgICAgfQoKICAgICAgICBjb3V0IDw8IG9kYmVkemllX3NpZSA8PCAnXG4nOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbWluKGlsZV9zYWwsIGlsZV9zcG90a2FuKTsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHNhbGVbaV0uZW1wdHkoKSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGZvciAoaW50IGo6IHNhbGVbaV0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNvdXQgPDwgaiA8PCAnICc7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGNvdXQgPDwgJ1xuJzsKICAgICAgICB9CiAgICAgICAgY291dCA8PCAnXG4nOwogICAgfQp9
MwoyIDMKMTE6MjAgMTI6MDAKMTE6MzAgMTE6NDAKMTE6NDAgMTE6NTUKMyA2CjE3OjE1IDE4OjMwCjE3OjIwIDE5OjAwCjE3OjE1IDE4OjAwCjE2OjU1IDE3OjU1CjE3OjEwIDE4OjEwCjE3OjAwIDE4OjAwCjIgNgowMTowMCAwMzowMAowMzowMCAwOTowMAowMTowMCAwNTowMAowNTowMCAwNzowMAowNzowMCAxMDowMAowOTowMCAxMDowMA==
3
2 3
11:20 12:00
11:30 11:40
11:40 11:55
3 6
17:15 18:30
17:20 19:00
17:15 18:00
16:55 17:55
17:10 18:10
17:00 18:00
2 6
01:00 03:00
03:00 09:00
01:00 05:00
05:00 07:00
07:00 10:00
09:00 10:00