B"Getting so far in this contest is not an easy feat. By solving all the previous problems, you have impressed the gods greatly. Thus, they decided to spare you the story for this problem and grant a formal statement instead. Consider n agents. Each one of them initially has exactly one item, i -th agent has the item number i . We are interested in reassignments of these items among the agents. An assignment is valid iff each item is assigned to exactly one agent, and each agent is assigned exactly one item. Each agent has a preference over the items, which can be described by a permutation p of items sorted from the most to the least desirable. In other words, the agent prefers item i to item j iff i appears earlier in the permutation p . A preference profile is a list of n permutations of length n each, such that i -th permutation describes preferences of the i -th agent. It is possible that some of the agents are not happy with the assignment of items. A set of dissatisfied agents may choose not to cooperate with other agents. In such a case, they would exchange the items they possess initially ( i -th item belongs to i -th agent) only between themselves. Agents from this group don't care about the satisfaction of agents outside of it. However, they need to exchange their items in such a way that will make at least one of them happier, and none of them less happy (in comparison to the given assignment). Formally, consider a valid assignment of items -- A . Let A(i) denote the item assigned to i -th agent. Also, consider a subset of agents. Let S be the set of their indices. We will say this subset of agents is dissatisfied iff there exists a valid assignment B(i) such that: An assignment is optimal if no subset of the agents is dissatisfied. Note that the empty subset cannot be dissatisfied. It can be proven that for each preference profile, there is"...