Secret Santa Pairing

You are given \(N\) employees. Each employee has a name and a department. You must assign a recipient to each employee as part of a Secret Santa exchange such that no one gives a gift to an employee in the same department.

Formally, you are given a permutation \(\pi\) of \(\{0,1,\ldots,N-1\}\) where employee \(i\) (with department \(D_i\)) is paired with employee \(\pi(i)\). The pairing is valid if for every \(i\), the department of employee \(\pi(i)\) is different from \(D_i\). If there exists a valid pairing, output the pairing in the format name -> name (one pairing per line, following the order of input). Otherwise, output No valid pairing.

inputFormat

The first line of input contains an integer \(N\) \((1 \le N \le 10^5)\) representing the number of employees. Each of the following \(N\) lines contains two strings: the employee's name and their department. Both strings consist of only letters.

outputFormat

If a valid pairing exists, output \(N\) lines. The \(i\)-th line (following the input order) should be in the format name -> name, indicating that the employee on the \(i\)-th input line gives a gift to the employee on the corresponding paired line. If no valid pairing exists, output a single line: No valid pairing.

3
alice accounting
bob accounting
charlie accounting

No valid pairing