CF1578K Kingdom of Islands
Description
The Kingdom of Islands consists of $ p $ islands. As the king, you rule over the whole kingdom, while each island is ruled over by one or several jarls under your rule. In total, there are $ n $ jarls under your jurisdiction.
Each island of the kingdom has its own strong traditions, so jarls that rule over the same island support each other and never have conflicts. The downsides of such strength are cultural conflicts between people inhabiting different islands. Thus, two jarls that rule over different islands are in conflict.
However, recent years brought a few changes to traditional relations between the jarls. To your knowledge, there are exactly $ k $ pairs of jarls such that relationships between two jarls in the pair are different from the traditional. That is, if two jarls of the pair you know rule over the same island, these jarls are in conflict. If they rule over different islands, then they overcome cultural disagreement and there is no conflict between them anymore.
As a true responsible king, you are worried about whether the kingdom is close to a major conflict. In order to estimate the current situation, you would like to find the largest possible group of jarls such that every two jarls in the group are in conflict.
Input Format
N/A
Output Format
N/A
Explanation/Hint
The conflict graph for the last sample testcase is given below. Each circle represents an island.
