Ну вот, вчера поспешил - людей насмешил)
Отправил решение и уехал, не учел вариант с циклами.
Сегодня подумал с абстрактной точки зрения - это же поиск компонент связности в двудольном графе.
Решается составлением списков связности и поиском в ширину / глубину за линейное время.
Решение получается значительно короче и проще:
https://pastebin.com/p8VNxYLLТесты:
https://pastebin.com/8jdCudCK