Сніг у Берляндії
Зими у Берляндії сніжні, і цьогорічна зима не виключення. Кожну зиму уряд країни вирішує задачу очистки доріг від снігу. І ця задача особливо складна для столиці.
Можна вважати, що столиця Берляндії складається з 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 (2 ≤ n ≤ 100, 0 ≤ m ≤ 5000, 1 ≤ A, B ≤ n, A ≠ B), де n — число перехресть у столиці Берляндії, m — число доріг. Наступні m рядків містять по чотири числа x_i, y_i, w_i, t_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i, 0 ≤ w_i ≤ 100, 0 ≤ t_i ≤ 1), де x_i, y_i — кінці дороги, w_i — кількість снігу на ній, t_i — тип дороги (0 означає, що дорога звичайна, 1 — історична). Між парою перехресть може бути не більше однієї дороги у кожному напрямку.
Вихідні дані
Виведіть p — максимальну кількість робочих днів. Наступні p рядків повинні містити опис щоденних маршрутів снігозбиральної машини. Маршрут виводьте як список номерів перехресть, який починається з A, завершується в B, відокремлених пропуском. Якщо є декілька розв'язків, виведіть довільну, якщо розв'язку немає, виведіть 0.