Un país tiene ciudades y n - 1 carreteras bidireccionales, cada una de las cuales conecta dos ciudades distintas. La red de carreteras es conexa: se puede llegar de cualquier ciudad a cualquier otra. Por lo tanto, cualesquiera dos ciudades están unidas por exactamente una ruta, es decir, un camino que no visita ninguna ciudad dos veces.
Cada carretera tiene un número entero no negativo de baches. El presidente quiere que toda ruta entre dos ciudades distintas sea lisa. Una ruta se llama lisa si el AND bit a bit de las cantidades de baches de sus carreteras es igual a su OR bit a bit (las operaciones bit a bit se recuerdan más abajo).
Una cuadrilla de obras puede repetir la siguiente operación cualquier número de veces:
Elegir dos ciudades distintas y y un entero i \ge 0, y en cada carretera de la ruta de a reemplazar la cantidad de baches por w \oplus 2^i (es decir, invertir el bit ).
Recordemos las definiciones. El bit número de un entero no negativo es su dígito binario en la posición de 2^i (el bit es el menos significativo).
El AND bit a bit de varios enteros tiene el bit igual a si y solo si el bit es igual a en todos ellos.
El OR bit a bit de varios enteros tiene el bit igual a si y solo si el bit es igual a en al menos uno de ellos.
El XOR bit a bit () de dos enteros tiene el bit igual a si y solo si el bit es distinto en esos dos enteros. En particular, w \oplus 2^i es con el bit invertido.
Encuentra el número mínimo de operaciones necesarias para que toda ruta entre dos ciudades distintas sea lisa.
La primera línea contiene un único entero (1 \le t \le 10^5) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene un único entero (1 \le n \le 2 \cdot 10^5) — el número de ciudades. Cada una de las siguientes n - 1 líneas contiene tres enteros , y (1 \le u, v \le n, u \ne v, 0 \le w < 2^{30}): una carretera entre las ciudades y con baches. Se garantiza que la red de carreteras es conexa.
La suma de sobre todos los casos de prueba no excede 2 \cdot 10^5.
Para cada caso de prueba imprime un entero — el número mínimo de operaciones.
Ejemplo 1
En el primer caso de prueba las ciudades forman una cadena 1 - 2 - 3 - 4 - 5 con 1, 0, 0, 1 baches en sus carreteras. Basta una operación: invertir el bit en la ruta de la ciudad a la ciudad . Entonces cada carretera tiene bache.
En el segundo caso de prueba una operación en la ruta de la ciudad a la ciudad con i = 2 convierte en , y las cuatro carreteras tienen baches.
En el tercer caso de prueba solo hay una ciudad, así que no hay rutas entre ciudades distintas y no hay que hacer nada.
En el cuarto caso de prueba la cadena 1 - 2 - 3 - 4 tiene baches. Bastan tres operaciones: la ruta 1 \to 3 con i = 0, la ruta 2 \to 3 con i = 1 y la ruta 1 \to 2 con i = 2. Entonces cada carretera tiene baches.
En el quinto caso de prueba la ciudad está unida a las ciudades , y , y las carreteras 2 - 3, 4 - 5 y 6 - 7 continúan las tres ramas. Las tres carreteras que salen de la ciudad tienen baches, y las tres exteriores tienen . Bastan dos operaciones: la ruta 2 \to 4 con i = 0 y la ruta 1 \to 6 con i = 0. Entonces cada carretera tiene bache. Se puede demostrar que una operación no es suficiente.