AIOC Banner

Problem: Choreography

Want to try solving this problem? You can submit your code online if you log in or register.


Choreography


Input File: dancein.txt
Output File: danceout.txt

Time Limit: 1 second


You are the long-suffering director of finance for the Australasian Academy of Aesthetic Arts, Astounding Acts of Acrobatics and Algebra. Week in, week out, the Academy organises increasingly elaborate and expensive arts events while you struggle to scrape together enough money to make ends meet.

The big thing this month is Machinations Infernal, a modern dance routine involving D dancers and H hula hoops. Each dancer is assigned a unique number between 1 and D, and starts off holding some number of hula hoops (possibly none). The dance routine is performed as a sequence of T throws where each throw is of the form "dancer i throws a hula hoop to dancer j" (where i and j represent different dancers). Each throw is performed in the order specified, one after another. No hoops may be thrown unless it is part of the routine.

For a dancer to throw a hula hoop, they clearly must hold at least one hoop at that instant. You have been tasked with determining how many hula hoops are needed at the start of the dance such that every dancer has one to throw when required by the routine. As everyone knows, hula hoops are very expensive, so you must determine the minimum number of hula hoops required for the dance routine.

For example, consider the following dance routine consisting of five dancers and eight throws.

1 → 3
2 → 3
2 → 1
5 → 2
3 → 5
1 → 4
3 → 4
4 → 5

One way to begin the routine is to give one hoop to dancer 1, two hoops to dancer 2, and one hoop to dancer 5. Dancers 3 and 4 begin with no hoops. The following table shows how many hoops each dancer has after each step of the dance.


Dancer
1 2 3 4 5
Initial set-up 1 2 0 0 1
1 → 3 0 2 1 0 1
2 → 3 0 1 2 0 1
2 → 1 1 0 2 0 1
5 → 2 1 1 2 0 0
3 → 5 1 1 1 0 1
1 → 4 0 1 1 1 1
3 → 4 0 1 0 2 1
4 → 5 0 1 0 1 2

With these four hoops, every dancer always has a hoop to throw when required and this in fact uses the fewest number of hoops possible.

Constraints

To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

Input

Your program should read from the file dancein.txt. The first line of this file will consist of the integers D and T separated by a single space. The following T lines describe the throws in the dance routine, in the order they must be performed. Each of these lines will be of the form `ai bi', specifying that dancer ai throws a hula hoop to dancer bi.

Output

Your program should write to the file danceout.txt. Your output file should consist of a single integer: the minimum number of hula hoops required for the dance.

Sample Input

5 8
1 3
2 3
2 1
5 2
3 5
1 4
3 4
4 5

Sample Output

4

Explanation

The sample input corresponds to the example on the previous page.

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 19 August 2019, 12:17pm AEST