Bucharest, Romania
October 23, 1999
|
Southeastern European
Regional Programming Contest
Bucharest, Romania October 23, 1999 |
Problem A
Circus, circus!
Source File: circuses.cc
Consider a town where all the streets are one-way and each street leads from one circus to another. It is known that by starting from a circus and wallking through town's streets, you can never again reach the same circus, i.e., the town's one-way streets form no cycles.
Your task is to write a program that finds the minimum number of people that can visit all the circuses of this town in such a way that no circus is visited by more than one person. Each circus-goer starts his trip from some circus (your algorithm should decide which) and can visit other circuses following the town's streets. There are no starting-circus restrictions.
Your program should read sets of data from a text file. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:
no_of_circuses_C
no_of_streets_S
Circus_At_Start_Of_Street_1 Circus_At_End_Of_Street_1
Circus_At_Start_Of_Street_2 Circus_At_End_Of_Street_2
...
Circus_At_Start_Of_Street_S Circus_At_End_Of_Street_S
The first line of each data set contains a positive integer no_of_circuses (C) (greater than 0 and less or equal to 120) which is the number of circuses in the town. The second line contains a positive integer no_of_streets (S) (possibly 0) which is the number of streets in the town. The next S lines represent the town's streets. The line corresponding to street k (k <= S) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= C) - the numberical identifier of the circus that is the start of the street, and Ek (1 <= Ek <= C) -- the numberical identifier of the circus that is the end of the street. Circuses are represented by integers ranging from 1 to no_of_circuses. There are no blank lines between consecutive sets of data and input data are correct.
The result of the program is to standard output. For each input data
set the program prints on a single line, starting from the beginnig of
the line, one integer: the minimum number of people required to visit all
the circuses in the town.