can u help me in this ??

Inspired by the example of that great Cornellian, Vladimir Nabokov,

some of your friends have become amateur lepidopterists (they study butterflies). Often when

they return from a trip with specimens of butterflies, it is very difficult for them to tell how

many distinct species they've caughtthanks to the fact that many species look very similar

to one another.

One day they return with n butterflies, and they believe that each belongs to one of two

different species, which we'll call A and B for purposes of this discussion. They'd like to

divide the n specimens into two groupsthose that belong to A and those that belong to

Bbut it's very hard for them to directly label any one specimen. So they decide to adopt

the following approach.

For each pair of specimens i and j, they study them carefully side by side. If they're confident

enough in their judgment, then they label the pair (i, j) either "same" (meaning they believe

them both to come from the same species) or "different" (meaning they believe them to come

from different species). They also have the option of rendering no judgment on a given pair,

in which case we'll call the pair ambiguous.

So now they have the collection of n specimens, as well as a collection of m judgments (either

"same" or "different") for the pairs that were not declared to be ambiguous. They'd like to

know if this data is consistent with the idea that each butterfly is from one of species A or

B. So more concretely, we'll declare the m judgments to be consistent if it is possible to

label each specimen either A or B in such a way that for each pair (i, j) labeled "same", it

1

is the case that i and j have the same label; and for each pair (i, j) labeled "different", it is

the case that i and j have different labels. They're in the middle of tediously working out

whether their judgments are consistent, when one of them realizes that you probably have an

algorithm that would answer this question right away.

Give an algorithm with running time O(m+n) that determines whether the m judgments are

consistent.