Firstly, we need to know the answer to the following question. For a given ~K~, is it possible to divide the fighters into two teams so that in the first ~K~ fights there are no confrontations of fighters from the same team?

Actually, we need to check whether a graph with ~N~ nodes (which represent fighters) and ~K~ edges (which represent fights) is bipartite. In other words, is it possible to paint its nodes with two colors so that the adjacent nodes are of different colors? We check this by actually painting the nodes: starting from node ~1~, we paint it white, then paint its neighbors black (because we have to), then paint its neighbors white (because we have to) and so on. This painting is done with BFS or DFS algorithm. The algorithm ends when we have either successfully painted all the nodes, which means the painting can be done, or when we've come across a contradiction: an adjacent node of the node ~X~ from which we're currently expanding is already painted the same color as ~X~, which means the painting is not possible.

Now it is clear that we are looking for the smallest ~K~ for which this procedure is going to fail. Testing out all possible ~K~ numbers is too slow. That is why we use binary search to find the value of the number ~K~.