AlgoLiga 2018

Paul Erdős (26 marca 1913 - 20 września 1996) był wybitnym węgierskim matematykiem. Zajmował się głównie teorią liczb, kombinatoryką i teorią grafów. Współpracował z wieloma matematykami i napisał ogrom prac. Stał się postacią na tyle kultową, że wprowadzono termin: liczba Erdősa. Sam Erdős ma liczbę Erdősa równą 0. Każdy naukowiec, który opublikował wspólnie z Erdősem jakąś pracę, ma liczbę Erdősa równą 1. Każdy naukowiec, który nie współpracował bezpośrednio z Erdősem, ale pisał pracę wspólnie z osobą która miała liczbę Erdősa równą 1, posiada liczbę Erdősa równą 2, i tak dalej. Jeśli danemu naukowcowi nie da się w ten sposób przypisać żadnej liczby Erdősa (na przykład publikował prace przez całe życie samemu) to ma on liczbę Erdősa równą nieskończoność. Twoim zadaniem jest wyznaczanie dla każdego naukowca jego liczby Erdősa na podstawie podanej bazy danych.

Wejście

Wejście rozpoczyna liczba naturalna 0 < M ≤ 10⁵ oznaczająca liczbę wpisów w bazie danych. Następnie jest M wierszy, z których każdy składa się z dwóch członów oddzielonych spacją. Pierwszy z nich to nazwa autora, a drugi to tytuł pracy której był (współ)autorem. Oba składają się ze znaków ASCII o kodach 32..125 . Tytuł publikacji rozpoczyna się i kończy znakiem " i składa się z co najwyżej 100 znaków. Nazwa autora składa się z co najwyżej 20 znaków i nie zawiera znaku spacji.

Paul Erdős zawsze występuje na wejściu pod nazwą "P.Erdos".

Wyjście

Na wyjście należy wypisać tyle wierszy ile na wejściu było różnych autorów. Każdy taki wiersz musi być postaci:

autor: jego_liczba_erdosa

Autorzy mają być wypisywani w kolejności leksykograficznej względem ich podanych nazw. W przypadku liczby Erdősa nieskończoność należy wypisać inf.

Przykład

Wejście:
18
W.Rytter "On polynomial-time approximation algorithms for the variable length scheduling problem"
E.Kopczynski "Definability of linear equation systems over groups and rings"
M.Pilipczuk "Breaking the 2^n-barrier for irredundance: two lines of attack"
P.Erdos "Regulare Graphen gegebener Taillenweite mit minimaler Knotenzahl"
M.Cygan "Breaking the 2^n-barrier for irredundance: two lines of attack"
R.Krishnamurti "On polynomial-time approximation algorithms for the variable length scheduling problem"
P.Erdos "Imbalances in k-colorations"
E.Gradel "Scott Finite model theory and its applications"
D.Kratsch "Breaking the 2^n-barrier for irredundance: two lines of attack"
E.Gradel "Definability of linear equation systems over groups and rings"
H.Sachs "Berge's theorem for the maximum charge problem"
R.Krishnamurti "Berge's theorem for the maximum charge problem"
D.Kratsch "Dieter Some extremal results in cochromatic and dichromatic theory"
H.Sachs "Regulare Graphen gegebener Taillenweite mit minimaler Knotenzahl"
J.Spencer "Scott Finite model theory and its applications"
J.Spencer "Imbalances in k-colorations"
P.Erdos "Dieter Some extremal results in cochromatic and dichromatic theory"
L.Godeaux "Les involutions cycliques appartenant a une surface algebrique"


Wyjście:
D.Kratsch: 1
E.Gradel: 2
E.Kopczynski: 3
H.Sachs: 1
J.Spencer: 1
L.Godeaux: inf
M.Cygan: 2
M.Pilipczuk: 2
P.Erdos: 0
R.Krishnamurti: 2
W.Rytter: 3