Rải sỏi ( STONE1 )

Giới hạn
  • Thời gian: 0.206s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Xét trò chơi rải sỏi với một người chơi như sau:

Cho cây T và một đống sỏi gồm K viên. Ở mỗi bước người ta lấy 1 viên sỏi từ đống sỏi và đặt vào một nút lá tuỳ ý. Nếu nút p có r nút lá và tất cả các nút lá đều đã có sỏi thì người ta gom tất cả các viên sỏi ở các nút lá lại, đặt 1 viên ở nút p, xoá các nút lá và trả r - 1 viên sỏi còn lại vào đống sỏi.

Trò chơi kết thúc khi đã đặt được 1 viên sỏi vào nút gốc

Yêu cầu: cho cây T, xác định số viên sỏi tối thiểu cần có để trò chơi có thể kết thúc. Cây có n nút (N <= 400), nút gốc được đánh số 1.

Input

  • Dòng đầu: số n.
  • Một số dòng tiếp theo, mỗi dòng có dạng: i m i1 i2 ... im. Trong đó m là số nút con của nút i; i1, i2, ..., im: các nút con của nút i.

Output

Số lượng viên sỏi ít nhất cần có.

Example

Input:
7
1 2 2 3
2 2 5 4
3 2 6 7

Output:
3


  • Người up: dtmp
  • Điểm: 0.25
  • Ngôn ngữ cho phép: