Сніг у Берляндії#4592
Зими в Берляндії сніжні, і нинішня зима не виняток. Щозими уряд країни вирішує задачу прибирання доріг від снігу. І це завдання особливо складне для столиці.
Вважається, що столиця Берляндії складається з перехресть і односторонніх доріг. Кожна дорога з'єднує два різних перехрестя x_i, y_i та спрямована від x_i до y_i. На -й дорозі лежить w_i тонн снігу.
Для прибирання доріг уряд найняв приватну компанію "Snow White". Щодня компанія надсилає одну снігоприбиральну машину. Вона починає роботу на перехресті з номером , проїжджає декілька перехресть до -го і зупиняється. Шлях машини може містити повторювані дороги і перехрестя, включаючи і .
Вантажівка за день долає шлях від перехрестя до перехрестя , водій, звичайно, не порушує правил дорожнього руху. Кожен проїзд машини по дорозі зі снігом зменшує кількість снігу на ній на тонну. Оскільки мешканці столиці можуть запідозрити уряд у марнотратстві бюджету, водієві заборонено їхати по дорозі, на якій немає снігу.
Деякі міські дороги мають історичну цінність, бо на них розташовані урядові будівлі. Тому після завершення роботи компанії "Snow White" ці дороги мають бути повністю очищені від снігу. Відомо, що на перехресті розташований історичний центр столиці, а це означає, що всі історичні дороги пішки досяжні з центру саме історичними дорогами. Пам'ятайте, що з точки зору пішохода дороги є двосторонніми.
Уряд платить компанії за кожен робочий день, тому керівництво "Snow White" зацікавлене у тому, щоб розтягнути роботу на якомога більшу кількість днів.
Ваше завдання — знайти послідовність маршрутів з в , які задовольняють обмеженням: дотримання напрямку руху, очищеність історичних доріг, максимальна кількість робочих днів.
Перший рядок містить цілі числа , , , (2 \le n \le 100, 0 \le m \le 5000, 1 \le A, B \le n, A \ne B), де — кількість перехресть у столиці Берляндії, — кількість доріг. Наступні рядків містять по чотири числа x_i, y_i, w_i, t_i (1 \le x_i, y_i \le n, x_i \ne y_i, 0 \le w_i \le 100, 0 \le t_i \le 1), де x_i, y_i — кінці дороги, w_i — кількість снігу на ній, t_i — тип дороги ( означає, що дорога звичайна, — історична). Між парою перехресть може бути не більше однієї дороги в кожному напрямку.
Виведіть — максимальну кількість робочих днів. Наступні рядків мають містити описи щоденних маршрутів снігоприбиральної машини. Маршрут виводьте як список номерів перехресть, починаючи з та закінчуючи , розділених пробілами. Якщо існує декілька рішень, виведіть будь-яке, якщо рішень немає, виведіть .
Приклад 1