Доставка подарунків
Обмеження: 2 сек., 256 МіБ
Перед Різдвом Санта Клаусу потрібно розвозити подарунки між деякими парами будинків у місті.
У місті, де Санта Клаус розвозить подарунки, є \(n\) будинків та \(m\) двосторонніх доріг між будинками. Від кожного будинку можливо добратися до кожного іншого будинку. Кожна дорога має своє значення \(c\) — яку максимальну кількість подарунків можна перевезти цією дорогою. Назвемо це значення пропускною можливістю. Відомо, що всі значення \(c\) різні.
Санта Клаус хоче проїхати \(q\) маршрутів між парами будинків \((a, b)\). Для кожного маршруту Санта Клаус робить такі обчислення.
Серед усіх маршрутів між парою будинків \((a, b)\) Санта Клаус вибирає такий, через який він може провезти чимбільше подарунків (нехай це значення — \(s\)). Санта Клаус може провезти шляхом деяку кількість подарунків, якщо він може провезти їх кожною дорогою цього шляху.
Санта Клаус видаляє дорогу, яка має пропускну можливість \(s\). Відомо, що така дорога існує та вона єдина, бо всі пропускні здатності унікальні. Ця дорога має мінімальну пропускну здатність на вибраному шляху.
Добавляє дорогу між будинками \(a\) та \(b\) з пропускною можливістю \(s\).
Гарантується, що після кожного запиту існує шлях між будь-якою парою будинків.
Санта Клаус просить вас порахувати значення \(s\) для кожного запиту \((a, b)\).
Вхідні дані
У першому рядку задано два натуральних числа \(n\) і \(m\) — кількість будинків та доріг.
У наступних \(m\) рядкаx містяться по три цілі числа \(u\), \(v\), \(c\) — існує дорога між будинками \(u\) й \(v\) з пропускною можливістю \(c\).
У наступому рядку задано натуральне число \(q\) — кількість запитів Санта Клауса.
У наступних \(q\) рядках містяться по два цілих числа \(a\), \(b\) — номери вершин, між якими рухається Санта Клаус.
Вихідні дані
Для кожного запиту виведіть одне значення \(s\) у новому рядку.
Обмеження
\(1 \leq n \leq 10^5\),
\(1 \leq m \leq 2 \cdot 10^5\),
\(1 \leq u, v \leq n\),
\(u \neq v\),
\(1 \leq c \leq 10^9\),
\(1 \leq q \leq 10^5\),
\(1 \leq a, b \leq n\),
\(a \neq b\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 1 2 2 2 3 3 3 1 4 1 4 1 2 1 2 3 4 | 3 1 |
Примітки
Після першого запиту Санта Клаус видаляє дорогу між будинками 2 й 3 з пропускною здатністю 3 та додає дорогу з такою ж пропускною здатністю між будинками 1 та 2.
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|