’What? Processors? Again?’. Well, I can hear you saying these kind of stuff already when you will have reached the end of the description – nothing more offensive I hope:). But don’t worry, this will be a much shorter description.

Description

In this project you are going to calculate the minimum time for a computer with infinitely many processors to complete a set of processes. This time no task scheduling is needed, so processes can be executed simultaneously. Plus, processes depend on each other. For example, you can’t process P1 before completing P2, if P1 depends of P2.

The goal of this project is you to learn implementing graphs in C++ and code a couple of graph algorithms. So you are expected to represent the system as a graph and work on it to make your life easier in following projects.

Input & Output

Input:

As usual you are going to be provided an input file as input which will be in the following format:

• In the first line, two integers V and E, which are the number of processes and dependencies, respectively. Note that process id’s are in {0,1,…V-1}
• In the following V lines one double per line which are time needed to complete each process, ordered by process id.
• In the following E lines two integers per line that represent the dependencies. Note that the second one depends on the first one.

Output:

As output you are expected to print just one double which is the minimum time required for server to complete all the processes.

An example is as follows:

Input File	Output File
8 95.1 2.2 6.3 8.4 3.57.612.74.80 11 22 32 43 74 54 75 76 5	29.5

Table 1: Sample Input and Output files