전쟁

2240년, 지구 연합군(EAF)과 화성 연방(MF) 사이에 거대한 전쟁이 벌어지고 있다. 최근까지 어느 쪽도 확실한 우위를 잡지 못했다. 그러나 최근의 재정 위기로 양측 모두 자원이 바닥나기 시작했고, MF는 이를 이용해 EAF의 영토를 잠식하고 있다. 이에 맞서 EAF는 전쟁 개시 이후 최대 규모의 작전을 감행하기로 한다. 화성 곳곳에 흩어진 MF의 모든 기지를 동시에 공격하는 것이다. EAF의 전력은 대부분 메카로 이루어져 있는데, 메카는 다리와 팔이 달린 비행 가능한 거대한 이족보행 병기다.

전형적인 MF 기지는 다음과 같이 구성된다. 기지를 이루는 건물들은 하나 이상의 영역(territory) 위에 배치된다. 각 영역은 방어막 탑(shield tower)이 만들어 내는 침투 불가능한 에너지 장(energy field)으로 외부 공격으로부터 보호된다. 방어막 탑들은 자신이 보호하는 영역 둘레에 배치된다.

각 방어막 탑은 지상 위에 건설된 채널(channel)을 통해 적어도 하나의 다른 탑과 연결된다. 연결된 탑들이 하나의 사이클(cycle)을 이루면 에너지 장이 생성된다. 하지만 사이클에 속한 채널 하나가 파괴되어 사이클이 끊기면, 그 에너지 장은 사라진다. 모든 에너지 장이 사라지면 기지는 손쉽게 함락된다. 그래서 채널로 연결된 두 탑은 그 채널을 방어한다. 각 탑은 일정 수의 적 메카를 막아 낼 수 있으며, 한 채널을 무너뜨리려면 그 채널이 연결하는 두 탑이 함께 막아 낼 수 있는 만큼의 메카가 필요하다. 즉 채널을 파괴하는 데 드는 비용은 두 탑 값의 합 $u_i + u_j$ 와 같다. 두 탑은 최대 하나의 채널로만 연결되며, 어떤 탑도 자기 자신과 연결되지 않는다.

(a) 하나의 채널로 연결된 두 탑. 꼭짓점은 탑을, 선은 두 탑을 잇는 채널을 나타낸다. 채널을 파괴하는 데 필요한 메카 수는 연결된 두 탑이 막아 낼 수 있는 메카 수의 합이다.

다만, 한 탑의 어느 한쪽 채널을 공격한다고 해서 그 탑이 다른 쪽에서 막아 낼 수 있는 메카 수가 줄어들지는 않는다. 각 채널의 비용은 독립적으로 두 탑 값의 합으로 계산된다.

(b) 여러 개의 에너지 장을 가진 MF 기지. 꼭짓점은 탑, 선은 탑을 잇는 채널이며, 숫자는 해당 탑이 막아 낼 수 있는 메카 수를 나타낸다.

(c) 이 경우 두 개의 채널을 파괴하면 모든 에너지 장이 사라진다. 이 전투에서 잃는 메카는 4대다.

기습 공격이므로 모든 채널 공격은 동시에 이루어진다. 즉 모든 채널이 같은 순간에 파괴된다. 기지를 무너뜨리려면 모든 에너지 장을 없애야 한다. 모든 채널을 부수면 목표는 달성되지만, 그러려면 너무 많은 메카를 희생해야 한다. EAF는 여유 병력이 거의 없으므로 메카를 최대한 효율적으로 투입해야 한다.

방어막 탑들의 그래프가 주어질 때, 모든 에너지 장을 사라지게 만들되 잃는 EAF 메카 수(파괴한 채널 비용의 합)가 최소가 되도록 하라. 그때 잃게 되는 메카의 최소 수를 구하라.

첫째 줄에 테스트 케이스의 수인 양의 정수 $n$ 이 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 기지에 있는 탑의 수인 양의 정수 $m$ ($2 < m \le 100$) 이 한 줄에 주어진다.
• 이어서 각 탑마다 두 줄이 주어진다.
  • 첫째 줄에는 세 양의 정수 $i$ ($0 \le i \le m-1$), $u_i$ ($1 \le u_i \le 50$), $c_i$ ($1 \le c_i \le m-1$) 가 공백으로 구분되어 주어진다. 각각 탑의 (식별) 번호, 그 탑이 막아 낼 수 있는 메카 수, 그리고 채널의 수다.
  • 둘째 줄에는 $c_i$ 개의 서로 다른 정수가 공백으로 구분되어 주어지며, 이는 탑 $i$ 와 연결된 탑들의 번호다.

각 테스트 케이스마다, 모든 에너지 장을 사라지게 하기 위해 전투에서 잃게 되는 EAF 메카의 최소 수를 한 줄에 하나씩 출력한다.