You’re some security analysts monitor a collection of networked computers, tracking the spread of an online virus. there are n computers in the system, call them c1,. you are given a trace indicating the times at which pairs of computers communicated. the trace consists of m triples (ci ,cj ,tk) that indicate that ci and cj communicated at time tk. at this time, a virus could have spread from ci to cj , or from cj to ci . we assume that the trace holds the triples sorted in order by time. for simplicity, we assume that each pair of computers communicates at most once over the time of the trace. also, it is possible to have pairs (cs ,cj ,tk) and (ct ,cj ,tk); this would indicate that cj opened connections to both cs and ct at time tk, allowing a virus to spread in any way among the 3 machines. there’s nothing special about 3 here – there might be 4 or 10 or however many connections open at the same time, allowing a virus to spread in any way among all of them. we would like to answer questions of the following form: if a virus was introduced at ci at time x, could it have spread to cj at time y? that is, is there a sequence of communications that could have led from the virus moving from ci to cj? design an algorithm that, given as input a collection of (sorted) trace data and a virus query, gives a yes/no answer for the query. the algorithm should run in time o(m+n).