Маршрутизація корів (Срібло)
Бесі набридла холодна зима, і вона вирішила вирушити на канікули в тепліший край. На жаль, єдина авіакомпанія, яка перевозить корів, — це Air Bovinia.
Air Bovinia має n літаків, кожен з яких обслуговує певний маршрут, що складається з двох або більше міст. Наприклад, літак може летіти за маршрутом, який починається в місті 1, потім прямує до міста 5, далі до міста 2, і завершує в місті 8. Жодне місто не повторюється в маршруті більше одного разу. Якщо Бесі обрала маршрут, вона може сісти на літак у будь-якому місті маршруту і вийти в будь-якому іншому місті цього ж маршруту. Наприклад, вона не зобов'язана починати подорож з першого міста маршруту і завершувати в останньому. Кожен маршрут має свою фіксовану вартість, яку Бесі повинна сплатити незалежно від кількості міст, які вона відвідає на маршруті. Якщо Бесі використовує певний маршрут кілька разів під час своєї подорожі (тобто, вона залишає маршрут і пізніше повертається на нього з іншого міста), вона повинна платити за кожне використання маршруту.
Бесі хоче знайти найдешевший спосіб дістатися від її ферми (міста A) до обраного «теплого місця» (міста B). Допоможіть їй визначити мінімальну вартість, яку вона повинна заплатити, а також мінімальну кількість різних польотів, які вона повинна здійснити, щоб досягти цієї мінімальної вартості.
Вхідні дані
Перший рядок вводу містить A, B, n (1 ≤ n ≤ 1000).
Наступні 2n рядків описують доступні маршрути, по два рядки на маршрут. Перший рядок містить вартість маршруту (ціле число в діапазоні 1.. 10^9) і кількість міст на маршруті (ціле число в діапазоні 1..100).
Другий рядок містить список міст у порядку проходження маршруту. Кожне місто позначається цілим числом у діапазоні 1..1000.
Рекомендується використовувати 64-бітні цілі.
Вихідні дані
Виведіть мінімальну вартість подорожі Бесі з міста A в місто B, а також мінімальну кількість польотів, необхідних для досягнення цієї мінімальної вартості. Якщо рішення не існує, виведіть -1 -1.