Mô tả và yêu cầu

Cách đây rất lâu trong một thiên hà xa có N hành tinh. Ngoài ra còn có N - 1 con
đường kết nối tất cả các hành tinh (trực tiếp hoặc gián tiếp). Nói cách khác, mạng
lưới các hành tinh và những con đường tạo thành một cây. Ngoài ra, mỗi con đường
dẫn liệt kê với một số nguyên biểu thị sự tò mò của con đường.
Một cặp hành tinh A, B thật nhàm chán nếu những điều sau đây là:
• A và B là các hành tinh khác nhau
• Đường đi giữa hành tinh A và B có thể sử dụng một hoặc nhiều đường
• XOR nhị phân của sự tò mò của tất cả các con đường đó bằng 0
Than ôi, thời thế đã thay đổi và một hoàng đế độc ác đang cai trị thiên hà. Ông ta
quyết định sử dụng Thần lực để phá hủy tất cả các con đường nối các hành tinh theo
một thứ tự nhất định.
Yêu cầu: Bạn hãy xác định số lượng cặp hành tinh nhàm chán trước khi hoàng đế
bắt đầu sự hủy diệt và sau khi mỗi lần phá hủy.

Dữ liệu vào

 Dòng đầu tiên của đầu vào chứa số nguyên N (1 <= N <= 100 000).
 Mỗi dòng trong số N - 1 dòng sau chứa ba số nguyên Ai, Bi, Zi (1 <= Ai; Bi
<= N, 0 <=Zi <= 1 000 000 000) biểu thị rằng hành tinh Ai và Bi được kết nối
trực tiếp với một con đường tò mò Zi.
 Dòng sau chứa hoán vị của N - 1 số nguyên đầu tiên biểu thị thứ tự trong đó
hoàng đế đang phá hủy các con đường. Nếu phần tử của hoán vị là j, thì hoàng
đế đã phá hủy con đường giữa hai hành tinh Aj và Bj trong cùng một bước.

Dữ liệu ra

 Đầu ra phải chứa N dòng, dòng thứ k chứa số cặp hành tinh buồn chán A, B
từ nhiệm vụ sau khi hoàng đế phá hủy đúng k - 1 con đường.

Giới hạn và chấm điểm

 20% tổng số điểm, nó sẽ giữ N <= 1 000.
 30% tổng số điểm, sự tò mò của mọi con đường sẽ bằng 0

Ví dụ

INPUT                    OUTPUT

                           2                        1
                           1 2 0                    0
                           1

                           3                        1
                           1 2 4                    0
                           2 3 4                    0
                           1 2

                           4                        6
                           1 2 0                    3
                           2 3 0                    1
                           2 4 0                    0
                           3 1 2

       Giải thích ví dụ đầu tiên: Trước khi bị hủy diệt, con đường giữa hành tinh 1
        và 2 rất nhàm chán. Sau hủy diệt, con đường giữa chúng không tồn tại nữa.
       Giải thích ví dụ thứ hai: Trước khi bị hủy diệt, một cặp hành tinh (1, 3) là
        nhàm chán. Con đường giữa 1 và 3 không còn có th                 ể xảy ra sau lần phá hủy
        đầu tiên và sau lần hủy diệt thứ hai, và không có cặp nào trong số các cặp còn
        lại của hành tinh là nhàm chán.
       Giải thích ví dụ thứ ba: Lưu ý rằng trong ví dụ này, mỗi cặp hành tinh có một
        đường đi có thể giữa chúng là nhàm chán bởi vì tất cả các con đường có sự tò
        mò 0.