Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P146PROB - ROUND 6B - Tấn công thành trì

Sau khi phá tan lũ quái vật ở vùng biên giới, nhà vua quyết định mở cuộc tấn công tới tận hang ổ của bọn chúng. Hệ thống phòng thủ của lũ quái vật rất kiên cố và phức tạp. Bọn chúng xây dựng các lâu đài, và giữa một số cặp lâu đài, chúng đắp thành lũy liên kết với nhau, để bảo vệ cho các đội quân nằm bên trong. Hang ổ của quân địch cứ tầng tầng lớp lớp.

Nhà vua đã vạch ra kế hoạch như sau:

Bước 1: Dùng máy bắn đá phá vỡ một số thành trì liên kết giữa các lâu đài của bọn chúng, sao cho không có đội quân nào của địch được bảo vệ kín bởi hệ thống thành trì.

Bước 2: Tiến công đánh giáp lá cà với quân địch.

Trong các lâu đài, lũ quái vật chuẩn bị rất nhiều các máy bắn đá. Để đảm báo phá được một thành lũy, nhà vua yêu cầu cần sử dụng số máy bắn đá bằng với tổng số máy bắn đá mà hai lâu đài ở 2 đầu thành lũy của địch. Chẳng hạn nếu lâu đài A có 5 máy bắn đá, lâu đài B có 3 máy bắn đá, để phá được bức tường thành nối lâu đài A và lâu đài B, đội quân của nhà vua cần sử dụng ít nhất 5+3 = 8 máy bắn đá.

Hình vẽ minh họa cho một hệ thống lâu đài + thành lũy của quân địch. Khi phá bức tường thành liên kết giữa 2 cặp lâu đài có số lượng máy bắn đá là (1,1), sẽ sử dụng số máy bắn đá là ít nhất (4 cái). Khi đó, không còn đội quân nào được bao bọc kín bởi thành lũy nữa, quân đội của nhà vua sẽ sẵn sàng vào tấn công giáp lá cà.

Các bạn hãy giúp nhà vua tính toán xem, cần sử dụng ít nhất bao nhiêu máy bắn đá để thực hiện được bước 1 của chiến dịch.

Input

Dòng đầu tiên là số lượng bộ test T (1 <= T <= 10).

Mỗi test gồm dòng đầu tiên gồm số nguyên m (2 <= m <= 100) là số lâu đài của quân địch.

Mỗi thành được biểu diễn bởi 2 dòng. Dòng đầu tiên gồm 3 số nguyên i (0 <= i <= m-1), u_i (1 <= u_i <= 50), c_i (1 <= c_i <= m-1) lần lượt là số hiệu của lâu đài, số máy bắn đá của địch có trong lâu đài và số thành lũy liên kết tới các lâu đài khác.

Dòng thứ hai gồm c_i số, thể hiện các lâu đài có thành lũy liên kết tới lâu đài i.

Output

Với mỗi test, in ra tổng số số máy bắn đá ít nhất cần sử dụng để thực hiện bước 1 của chiến dịch.

Example

Input:
1
3
0 1 2
1 2
1 2 2
0 2
2 3 2
0 1 Output: 3

Được gửi lên bởi:adm
Ngày:2014-03-11
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2018-05-24 17:32:35
Dùng vector thì nhớ clear nhé ^^
2017-07-27 15:34:38
P146PROB: https://e16cn-ptit.blogspot.com/2017/12/p146prob-round-6b-tan-cong-thanh-tri.html

Last edit: 2017-12-13 22:52:21
2016-08-07 15:08:05
Có ai làm bài này rồi có thể chia sẻ cho mình cách giải quyết vấn đề không?
2016-04-02 19:18:48
nhin de da ko muon lam @@
2014-11-29 08:22:38 Bác Ba Phì


Last edit: 2014-12-01 02:26:21
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.