SKIVER1 - Skiers

Vương quốc nọ có N thành phố, biết rằng thành phố 1 chỉ có thể đến được các thành phố khác mà không thành phố nào đến được thành phố 1, thành phố N không đến được thành phố nào khác mà chỉ có thành phố khác đến thành phố này. Trong vương quốc 2 thành phố bất kì được nối với nhau thông qua không quá 1 con đường một chiều. Quanh năm vương quốc ngập trong tuyết, nhà vua muốn tuyển một đội trượt tuyết gồm ít người nhất sao cho mỗi người đều xuất phát từ thành phố 1, qua các thành phố trung gian rồi dừng lại tại thành phố N thỏa mãn các con đường một chiều được thăm bởi ít nhất 1 thành viên trong đội.

Dữ liệu

  • Dòng đầu ghi số nguyên dương N, số thành phố (N < 5001).
  • N -1 dòng sau mỗi dòng mô tả thông tin về mỗi thành phố từ 1 đến N - 1, số đầu tiên của mỗi dòng ghi số K là lượng thành phố mà thành phố đó có thể đi tới, K số tiếp theo là chỉ số các thành phố đó.

Kết qủa

Ghi ra số nhỏ nhất các thành viên trong đội.

Ví dụ

 
Dữ liệu: 
15
5 3 5 9 2 4
1 9
2 7 5
2 6 8
1 7
1 10
2 14 11
2 10 12
2 13 10
3 13 15 12
2 14 15
1 15
1 15
1 15
Kết qủa 
8 


Added by:Trần Hải Đăng
Date:2010-05-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6
Resource:Chút thay đổi từ bài POI 2001

hide comments
2012-12-04 12:28:12 TINYJR
sample output should be 3..
maybe the data were wrong?

Last edit: 2012-08-21 12:46:09
2012-12-04 12:28:12 Trần Hải Ðãng
Statement updated.
2012-12-04 12:28:12 Robert Gerbicz
Please provide English problem's description!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.