A large number n of dinosaur bones are discovered at an archeological site, and each bone is labeled by a distinct integer in {1, 2, . . . , n}. Researchers examine some pairs of these bones to try to determine the number of different species of dinosaurs the bones come from. From this examination, they create a list L that contain a total of m items: each item in L is of the form S(i, j), which means the bone labelled i and the bone labelled j are from the same specie, or of the form D(k, l), which means that the bone labelled k and the bone labelled l are from different species. But, unfortunately, researchers may make mistakes: for example, they could create a list L = . . . , S(3, 2), . . . , D(5, 2), . . . , S(5, 3), . . . which must be incorrect (do you see why?).

Design an efficient algorithm for the following task:

The algorithms input is a list L of m items as described above, where m n.

(Recall that n is the total number of bones that were discovered.)

If the list L is incorrect (as explained above)

then the algorithm outputs Error Found

else the algorithm outputs an integer k, where k is the maximum possible number of different species the bones are from, according to the input list L.

Describe your algorithm in clear and concise English and analyze its worst-case time complexity. The worst-case running time of your algorithm must be asymptotically better than O(mn).