You are helping some security analysts monitor a collection of networked computers, tracking the spread of an online virus. There are n computers in the system, labeled C 1 , C 2 , ..., C n , and as input, you are given a collection of trace data indicating the times at which pairs of computers communicated. Thus the data is a sequence of ordered triples (C i , C j , t k ). Such a triple indicates that C i and C j communicated at time t k . Assume there are m triples total. Now let us assume that the triples are presented to you in sorted order of time. For purposes of simplicity, we will assume that each pair of computers communicates at most once during the interval you are observing. The security analysts you are working with would like to be able to answer questions of the following form: If the virus was inserted into computer C a at time x, could it possibly have infected computer C b by time y? The mechanics of infection are simple, if an infected computer C i communicates with an uninfected computer C j at time t k , (in other words, if one of the triples (C i , C j , t k ) or (C j , C i , t k ) appears in the trace data), then computer C j becomes infected as well, starting at time t k . Infection can thus spread from one machine to another across a sequence of communications, provided that no step in this sequence involves a move backwards in time. Thus, for example, if C i is infected by time t k and the trace data contains triples (C i , C j , t k ) and (C j , C q , t r ), where t k t r , then C q will become infected via C j . (Note that it is okay for t k to be equal to t r . This would mean that C j had open connections to both C i and C q at the same time, so a virus could move from C i to C q .) For example, suppose n = 4, the trace data consists of the triples (C 1 , C 2 , 4), (C 2 , C 4 , 8)(C 3 , C 4 , 8)(C 1 , C 4 , 12), and the virus was inserted into computer C 1 at time 2. Then C 3 would be infected at time 8 by a sequence of three steps-first C 2 becomes infected at time 4, then C 4 gets the virus from C 2 at time 8, and then C 3 gets the virus from C 4 at time 8. On the other hand, if the trace data were (C 2 , C 3 , 8)(C 1 , C 4 , 12)(C 1 , C 2 , 14), and again the virus was inserted into computer C 1 at time 2, then C 3 would not become infected during the period of observation. Observe, however, that although C 2 becomes infected at time 14, C 3 only communicates with C 2 before C 2 becomes infected. There is no sequence of communi- cations moving forward in time by which the virus could get from C 1 to C 3 in this second example. Design an algorithm that answers questions of this type: given a collection of trace data, the algorithm should decide whether a virus introduced at computer C a at time x could have infected computer C b by time y. Prove that the algorithm runs in time O(m). Also, prove the correctness of your algorithm.