Цветные волшебники

помощь с задачей на с++

41. Цветные волшебники
Сказочная страна представляет собой множество городов, соединенных
дорогами с двухсторонним движением. Причем из любого города страны можно
добраться в любой другой город либо непосредственно, либо через другие
города. Известно, что в сказочной стране не существует дорог, соединяющих
город сам с собой и между любыми двумя разными городами, существует не
более одной дороги.
В сказочной стране живут желтый и синий волшебники. Желтый волшебник,
пройдя по дороге, перекрашивает ее в желтый цвет, синий в синий. Как
известно, при наложении желтой краски на синюю, либо синей краски на
желтую, краски смешиваются и превращаются в краску зеленого цвета, который
является самым нелюбимым цветом обоих волшебников.
В этом году в столице страны (городе F) проводится конференция волшебников.
Поэтому желтый и синий волшебники хотят узнать, какое минимальное
количество дорог им придется перекрасить в зеленый цвет, чтобы добраться в
столицу. Изначально все дороги не покрашены.
Начальное положение желтого и синего волшебников заранее не известно.
Поэтому необходимо решить данную задачу для k возможных случаев их
начальных расположений.
Вход. Первая строка содержит целые числа n (1 ≤ n ≤ 105) и m (1 ≤ m ≤ 500000)
– количество городов и дорог в волшебной стране соответственно. Третья
строка содержит одно целое число F (1 ≤ F ≤ n) – номер города, являющегося
столицей сказочной страны. В следующих m строках находится описание дорог
страны. В этих m строк записано по два целых числа ai и bi, означающих, что
существует дорога, соединяющая города ai и bi. Следующая строка содержит
целое число k (1 ≤ k ≤ 105) – количество возможных начальных расположений
волшебников. Далее следуют k строк, каждая из которых содержит два целых
числа – номера городов, в которых изначально находится желтый и синий
волшебники соответственно.
Выход. Для каждого из k тестов вывести минимальное количество дорог,
которое придется покрасить в зеленый цвет волшебникам для того чтобы
добраться в столицу.
Пример входа
6 6
1
1 2
2 3
3 4
4 2
4 5
3 6
2
5 6
6 6
Пример выхода
1
2

0

Сообщение от sonyagal Вход. Первая строка содержит целые числа n (1 ≤ n ≤ 105) и m (1 ≤ m ≤ 500000) – количество городов и дорог в волшебной стране соответственно. Третья строка содержит одно целое число F (1 ≤ F ≤ n) – номер города, являющегося столицей сказочной страны

что тогда содержится во второй строке, которая у вас в примере показана?

0

Да не третья там строка, а вторая. Почти везде в условии одна и та же "ошибка".
Правильный текст нашел тут: https://algocode.ru/files/cour... 602-ru.pdf

Добавлено через 57 минут
sonyagal, есть "подсказка" (для частного случая).
Если два целых числа yel и blu - номера городов, в которых изначально находится желтый и синий волшебники соответственно, то при выполнении условия
ответом будет 0.

Можно сделать функцию, например, int MinGreenCountPath (int n, int m, int f, int *a, int *b, int yel, int blu), которая находит минимальное количество зеленых дорожек для определенных значений yel и blu, а потом в цикле k раз "прогнать" функцию для различных значений yel и blu. Либо сразу в функцию передавать (указатели на) массивы значений yel и blu (а также значение k).
a и b - массивы дорог. Как вариант, объединить эти два массива в один размером 2 * m (или m * 2).

Добавлено через 3 часа 12 минут
Идея: использовать как-то булеву "диагональную таблицу" (для указанного примера)
Где в i-ой строке (нумерация с единицы, как и у столбцов) указано, есть ли дорога (из города i) в j-ый город (и наоборот), j - номер столбца. Значение равно 1 - есть дорога, 0 - нет.
Например, первая строка означает, что из города №1 есть дорога (двусторонняя) только в город №2, из города №2 - в города №3 и 4 (и т. д.).

P. S.: наверняка есть подходящий готовый алгоритм, но я в этом мало что понимаю.

1