Побітові вибоїни#13103

Побітові вибоїни

4 секунди
256 мегабайтів

У країні є міст і n - 1 двосторонніх доріг, кожна з яких сполучає два різні міста. Дорожня мережа зв'язна: з будь-якого міста можна дістатися до будь-якого іншого. Отже, будь-які два міста сполучає рівно один маршрут — шлях, який не проходить жодним містом двічі.

На кожній дорозі є невід'ємна ціла кількість вибоїн. Президент хоче зробити гладким кожен маршрут між двома різними містами. Маршрут називається гладким, якщо побітове AND кількостей вибоїн на його дорогах дорівнює їхньому побітовому OR (побітові операції нагадано нижче).

Дорожня бригада може будь-яку кількість разів повторювати таку операцію:

Нагадаємо означення. Біт номер невід'ємного цілого числа — це його двійкова цифра на позиції 2^i (біт — наймолодший).

Знайдіть мінімальну кількість операцій, потрібну, щоб зробити гладким кожен маршрут між двома різними містами.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^5) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить одне ціле число (1 \le n \le 2 \cdot 10^5) — кількість міст. Кожен із наступних n - 1 рядків містить три цілі числа , і (1 \le u, v \le n, u \ne v, 0 \le w < 2^{30}): дорогу між містами і з вибоїнами. Гарантується, що дорожня мережа зв'язна.

Сума за всіма тестовими випадками не перевищує 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — мінімальну кількість операцій.

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку міста утворюють ланцюжок 1 - 2 - 3 - 4 - 5, а на його дорогах 1, 0, 0, 1 вибоїн. Достатньо однієї операції: змінити біт на маршруті від міста до міста . Тоді на кожній дорозі буде вибоїна.

У другому тестовому випадку одна операція на маршруті від міста до міста з i = 2 перетворює на , і на всіх чотирьох дорогах стає по вибоїн.

У третьому тестовому випадку є лише одне місто, тож маршрутів між різними містами немає і нічого робити не потрібно.

У четвертому тестовому випадку на ланцюжку 1 - 2 - 3 - 4 є вибоїн. Достатньо трьох операцій: маршрут 1 \to 3 з i = 0, маршрут 2 \to 3 з i = 1 і маршрут 1 \to 2 з i = 2. Тоді на кожній дорозі буде вибоїн.

У п'ятому тестовому випадку місто сполучене з містами , і , а дороги 2 - 3, 4 - 5 і 6 - 7 продовжують три гілки. На трьох дорогах біля міста немає вибоїн, а на трьох зовнішніх — по вибоїні. Достатньо двох операцій: маршрут 2 \to 4 з i = 0 і маршрут 1 \to 6 з i = 0. Тоді на кожній дорозі буде вибоїна. Можна показати, що однієї операції недостатньо.