eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сніг у Берляндії

Сніг у Берляндії

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Зими у Берляндії сніжні, і цьогорічна зима не виключення. Кожну зиму уряд країни вирішує задачу очистки доріг від снігу. І ця задача особливо складна для столиці.

Можна вважати, що столиця Берляндії складається з n перехресть та m одностороніх доріг. Кожна дорога з'єднує два різних перехрестя x_i, y_i і направлена від x_i до y_i. На i-ій дорозі лежить w_i тон снігу.

Для очистки доріг уряд найняв приватну компанію "Snow White". Кожен день компанія висилає одну снігозбиральну машину. Вона починає роботу на перехресті з номером A, проходить декілька перехресть до B-го і зупиняється. Шлях машини може містити дороги і перехрестя, що повторюються, включаючи A та B.

Вантажівка за день робить шлях від перехрестя A до перехреся B, водій, звичайно ж, не порушує правил дорожного руху. Кажен прохід машини по дорозі зі снігом зменшує кількість снігу на ній на 1 тону. Так як жителі столиці можуть звинуватити уряд у марнотратстві бюджету, водію заборонено вести машину по дорозі, на якій немає снігу.

Деякі міські дороги є історичними цінностями, тому що на них стоять урядові будівлі. Тому по завершенню роботи компанії "Snow White" ці дороги повинні бути вільні від снігу. Відомо, що на перехресті A знаходиться історичний центр столиці, що означає пішохідну досяжність усіх історичних доріг з центру по історичним дорогам. Пам'ятайте, що з точки зору пішоходу дороги є двосторонніми.

Уряд платить компанії за кожен день роботи, тому керівництво "Snow White" зацікавлено у тому, щоб ростягнути роботу на найбільшу кількість днів.

Ваша задача — знайти послідовність маршрутів з A в B, які задовольняють обмеженням: обмеження напрямку руху, чистота історично значимих доріг, максимальна кількість робочих днів.

Вхідні дані

Перший рядок містить ціліе числа n, m, A, B (2n100, 0m5000, 1A, Bn, AB), де n — число перехресть у столиці Берляндії, m — число доріг. Наступні m рядків містять по чотири числа x_i, y_i, w_i, t_i (1x_i, y_in, x_iy_i, 0w_i100, 0t_i1), де x_i, y_i — кінці дороги, w_i — кількість снігу на ній, t_i — тип дороги (0 означає, що дорога звичайна, 1 — історична). Між парою перехресть може бути не більше однієї дороги у кожному напрямку.

Вихідні дані

Виведіть p — максимальну кількість робочих днів. Наступні p рядків повинні містити опис щоденних маршрутів снігозбиральної машини. Маршрут виводьте як список номерів перехресть, який починається з A, завершується в B, відокремлених пропуском. Якщо є декілька розв'язків, виведіть довільну, якщо розв'язку немає, виведіть 0.

Приклад

Вхідні дані #1
4 7 1 4
1 2 3 1
2 1 100 0
2 4 1 0
1 3 1 0
3 4 4 0
2 3 2 1
1 4 2 0
Вихідні дані #1
6
1 3 4
1 4
1 4
1 2 4
1 2 3 4
1 2 3 4