Задача . I. Экскурсии

Ирина работает в экскурсионной компании Саратова. Сегодня она собирается организовать экскурсии по городам Саратов и Энгельс.

Всего существует \(n_1\) достопримечательность в Саратове и \(n_2\) достопримечательность в Энгельсе. Города разделены рекой, но есть \(m\) автобусных маршрутов, которые проходят по мостам и позволяют туристам добраться из Саратова в Энгельс и обратно. Маршрут \(i\)-го автобуса проходит от \(x_i\)-й достопримечательности в Саратове до \(y_i\)-й достопримечательности в Энгельсе, а также в обратном направлении.

Ирина хочет спланировать экскурсии на текущий день. Экскурсионные поездки начинаются в Саратове утром, продолжаются в Энгельсе днем и заканчиваются в Саратове вечером.

Каждый турист начинает свой экскурсионный день с какой-нибудь достопримечательности Саратова, \(k_i\) туристов начинают с \(i\)-й достопримечательности. Затем гиды везут их в Энгельс: на каждой достопримечательности Саратова гид выбирает автобусный маршрут, ведущий от этой достопримечательности в Энгельс, и все туристы, отправляющиеся с этой достопримечательности, отправляются в Энгельс по этому автобусному маршруту. После завершения экскурсий в Энгельсе происходит то же самое: для каждой достопримечательности в Энгельсе гид выбирает автобусный маршрут, ведущий от этой достопримечательности в Саратов, и все туристы с этой достопримечательности отправляются в Саратов по этому автобусному маршруту.

Этот процесс может привести к такой ситуации, что некоторые туристы вернутся к той же достопримечательности в Саратове, с которой они начали утром. Очевидно, туристам это не нравится, поэтому Ирина хочет выбрать, куда гиды повезут туристов (как по дороге из Саратова в Энгельс, так и по дороге из Энгельса в Саратов), чтобы минимально возможное количество туристов вернулось к той же достопримечательности, с которой они начали. Помогите Ирине найти оптимальный план!