Here is the link to the question BUg’s Life on SPOJ [BUGLIFE][1]. I know that this is based on bfs and graph coloring. But only one thing I am unable to understand. Suppose we take a test case where number of bugs is 6 and number of interaction is 3. and the interactions are as follows.

1 2

3 4

5 6

So here how will we do a bfs? Because here we have 3 separate graphs 1->2,3->4,5->6. How can we have the link to these 3 separate graphs or anyother methods? The testcase is for exampls in general the no. of nodes of the 3 separate graphs could be many.

[1]: SPOJ.com - Problem BUGLIFE