Celebrity P86176


Statement
 

pdf   zip

In a party, we say that cc is a celebrity if everybody knows cc, but cc knows nobody. (We do not care if cc knows himself or herself.) Please write a program to tell if a party has a celebrity.

The party has nn persons, each with a first name fif_i and a surname sis_i. All those 2n2n strings have the same length mm, and implicitly tell who knows who in a funny way. Given two characters aa and bb, let us define the “distance” between them as d(a,b)=(ab+12)mod2612d(a, b) = (a - b + 12) \bmod 26 - 12. Observe that 12d(a,b)13-12 \le d(a, b) \le 13. Now, given a first name fif_i and a surname sjs_j, let us define the “total distance” between them as t(fi,sj)=0k<md(fi[k],sj[k])t(f_i, s_j) = \sum_{0 \le k < m} d(f_i[k], s_j[k]). Then, ii knows jj if and only if t(fi,sj)>0t(f_i, s_j) > 0.

For instance, consider a small party with two persons with short names: Li Hu and No Hi. Since $d(`\texttt{\small L}', `\texttt{\small H}') = 4$ and $d(`\texttt{\small i}', `\texttt{\small i}') = 0$, we have $t(``\texttt{\small Li}'', ``\texttt{\small Hi}'') = 4 > 0$, so Li Hu does know No Hi. By contrast, $t(``\texttt{\small No}'', ``\texttt{\small Hu}'') = 0$, so No Hi does not know Li Hu.

Input

Input consists of several cases. Every case begins with nn, followed by nn names (first name and surname). All the given strings have the same length mm. The first letter of each string is uppercase, the rest are lowercase. First names and surnames can be repeated, but the composition of them uniquely identifies one person. Assume 2n1052 \le n \le 10^5 and 2m62 \le m \le 6.

Output

Print one line for every case. If the party has no celebrity, print “No”. If the party has one celebrity, print his or her name. If the party has more than one celebrity, print “I should learn some logic”.

Public test cases
  • Input

    2
    Li Hu
    No Hi
    2
    John York
    Elsa Pope
    4
    Pam Kim
    Max Kim
    Ann Oak
    Ada Hay
    

    Output

    No Hi
    No
    Ann Oak
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++