Polish version    English version  
  History of OI -> IX OI 2001/2002 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Rules
For contestants
Helpful resources
Stats
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
IX Olimpiada Informatyczna 2001/2002

Task: nar
Author: Piotr Chrz±stowski-Wachtel
Skiers

III stage contest  

On the south slope of Bytemount there is a number of ski tracks and one ski lift. All the tracks run from the top station of the ski lift to the bottom one. Every morning a group of ski lift workers examines the condition of the tracks. They together take the lift up to the top station, and next each of them skis down along a chosen track to the bottom station. Each worker skis down only once. The tracks of the workers may partially be the same. Each track examined by any of the workers leads always downwards.

The map of ski tracks consists of a network of clearings connected by cuttings in the forest. Each clearing lies on different height. Any two clearings may be directly connected by at most one cutting. Skiing down from the top to the bottom station one can choose a track to visit any one clearing (although probably not all of them in a single run). Ski tracks may cross only on clearings and do not run through tunnels nor on bridges.

Task

Write a program which:
  • reads from the text file nar.in the map of ski tracks,
  • computes the minimal number of workers to examine all the cuttings between the clearings,
  • writes the result to the text file nar.out.

Input

In the first line of the input file nar.in there is one integer n equal to the number of clearings, 2<=n<=5 000. The clearings are numbered from 1 to n.

Each of the successive n-1 lines contains a sequence of integers separated by single spaces. The integers in the (i+1)-st line of the file specify which clearings the cuttings from the clearing number i lead down to. The first integer k specifies the number of those clearings. The successive k integers are their numbers ordered in the direction from west to east, according to the arrangement of the cuttings leading to them. The top station of the ski lift lies on the clearing number 1, and the bottom one on the clearing number n.

Output

In the first and only line of the output file nar.out there ought to be exactly one integer - the minimal number of workers that are able to examine all the cuttings in the forest.

Example

For the following input file nar.in:
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

[ map of ski tracks ]

the correct answer is in the following output file nar.out:
8



Print friendly version