Bit düzeyinde çukurlar#13103

Bit düzeyinde çukurlar

4 saniye
256 megabayt

Bir ülkede şehir ve her biri iki farklı şehri birbirine bağlayan n - 1 çift yönlü yol vardır. Yol ağı bağlantılıdır: herhangi bir şehirden herhangi bir başka şehre gidilebilir. Dolayısıyla herhangi iki şehir tam olarak bir rota ile birleşir; rota, hiçbir şehirden iki kez geçmeyen bir yoldur.

Her yolda negatif olmayan tam sayıda çukur vardır. Başkan, iki farklı şehir arasındaki her rotayı düzgün hâle getirmek istiyor. Bir rota, üzerindeki yolların çukur sayılarının bit düzeyinde AND'i bit düzeyinde OR'una eşitse düzgün olarak adlandırılır (bit düzeyindeki işlemler aşağıda hatırlatılmıştır).

Bir yol ekibi aşağıdaki işlemi istediği kadar tekrarlayabilir:

Tanımları hatırlayalım. Negatif olmayan bir tam sayının numaralı biti, onun 2^i konumundaki ikilik basamağıdır ( numaralı bit en düşük anlamlı bittir).

İki farklı şehir arasındaki her rotayı düzgün hâle getirmek için gereken en az işlem sayısını bulun.

Giriş

İlk satırda bir tam sayı (1 \le t \le 10^5) — test durumlarının sayısı verilir.

Her test durumunun ilk satırında bir tam sayı (1 \le n \le 2 \cdot 10^5) — şehirlerin sayısı verilir. Sonraki n - 1 satırın her biri üç tam sayı , ve (1 \le u, v \le n, u \ne v, 0 \le w < 2^{30}) içerir: ve şehirleri arasında çukuru olan bir yol. Yol ağının bağlantılı olduğu garanti edilir.

Tüm test durumları üzerinden değerlerinin toplamı 2 \cdot 10^5'i aşmaz.

Çıktı

Her test durumu için bir tam sayı — en az işlem sayısını yazdırın.

Örnekler

Örnek 1

Loading
Loading

Not

Birinci test durumunda şehirler 1 - 2 - 3 - 4 - 5 zincirini oluşturur ve yollarında 1, 0, 0, 1 çukur vardır. Bir işlem yeterlidir: numaralı şehirden numaralı şehre giden rotada numaralı biti tersine çevirmek. O zaman her yolda çukur olur.

İkinci test durumunda numaralı şehirden numaralı şehre giden rotada i = 2 ile yapılan bir işlem sayısını yapar ve dört yolun hepsinde çukur olur.

Üçüncü test durumunda yalnızca bir şehir vardır, bu yüzden farklı şehirler arasında rota yoktur ve hiçbir şey yapmaya gerek yoktur.

Dördüncü test durumunda 1 - 2 - 3 - 4 zincirinde çukur vardır. Üç işlem yeterlidir: i = 0 ile 1 \to 3 rotası, i = 1 ile 2 \to 3 rotası ve i = 2 ile 1 \to 2 rotası. O zaman her yolda çukur olur.

Beşinci test durumunda numaralı şehir , ve numaralı şehirlere bağlıdır ve 2 - 3, 4 - 5 ile 6 - 7 yolları üç dalı devam ettirir. numaralı şehirden çıkan üç yolda çukur, dıştaki üç yolda ise çukur vardır. İki işlem yeterlidir: i = 0 ile 2 \to 4 rotası ve i = 0 ile 1 \to 6 rotası. O zaman her yolda çukur olur. Bir işlemin yeterli olmadığı gösterilebilir.