Foreign Exchange (Editorial)

For the exchange program to be successfully implemented, every student who wants to move from $A$ to $B$ must have another student who wants to move from $B$ to $A$. In other words, each pair $(A,B)$ must have a corresponding reverse pair $(B,A)$. Identical pairs may appear multiple times.

We'll use a multiset to store the pairs. The algorithm works as follows:

• For each input pair $(А,В)$, check whether the pair $(B,A)$ is present in the multiset.

• If such a pair is found, remove it from the multiset, thereby forming a valid exchange pair.

• If the reverse pair does not exist, add the current pair $(A,B)$ to the multiset.

After processing all the students, there are two possible cases:

• The multiset is empty — this means that for every pair $(A,B)$, a corresponding reverse pair $(B,A)$ was found, and the exchange program can be successfully carried out.

• The multiset is not empty — this means that some students do not have a suitable partner, and the exchange program cannot be completed.

Based on this, the output is either "YES" or "NO".

Example

In the first test, every pair $(A,B)$ has a corresponding reverse pair $(B,A)$. In the second test, none of the students' requests can be fulfilled.

Algorithm implementation

Declare a multiset of pairs $s$. During execution, it will store only those pairs $(A,B)$ for which a corresponding reverse pair $(B,A)$ has not yet been found.

multiset<pair<int,int> > s;

Read the number of test cases $t$.

scanf("%d",&t);

Process the $t$ test cases sequentially.

while (t--)
{

Read the number of students $n$.

  scanf("%d", &n); 

Before processing each test case, clear the multiset.

  s.clear();

Process the students' requests sequentially.

  for (i = 0; i < n; i++)
  {

Read the pair $(a,b)$ and look for a student with the opposite exchange direction.

    scanf("%d %d", &a, &b);
    auto it = s.find({ b, a });

If the reverse pair is not found, the current pair $(a,b)$ is added to the multiset $s$.

If the reverse pair is found, it is removed from $s$, since a partner for this exchange has been found.

Thus, $s$ always contains only those pairs for which a match has not yet been found.

    if (it == s.end()) s.insert({ a, b });
    else s.erase(it);
  }

If, after processing all students, the multiset is empty, it means that a reverse pair was found for every pair, and the exchange program can be successfully carried out. Otherwise, print "NO".

  if (s.empty()) printf("YES\n");
  else printf("NO\n");
}