FasterHarder:
вот это, пожалуй, остался единственный момент в этой задаче, с которым бы разобраться

на мое ИМХО, "чей ход" вообще учитывать НЕ нужно.
мы ведь раскрашиваем граф как бы волнами (через BFS, наверное, надо будет сделать), где эпицентром является один из тупиков.
и в конце концов волны доходят до стартовой вершины и все.
и вроде достаточно просто посмотреть на:


т е раскраска автоматически чередует ходы игроков и дополнительно это уже не надо анализировать...
прикладываю картинку-доказательство)
_____________________.png (, : 86)

p.s. может быть я здесь сильно ошибаюсь и поторопился с таким выводом

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845444