Ho is an expert in martial arts called . She runs a Taebo school, and there are students in her school. Since Ho is too old to teach Taebo, she is going to hand over her school to one of her students. To find a suitable candidate, Ho made all pairs of students do a Taebo matchup with each other, and wrote all the results. In a Taebo matchup, exactly one person wins the match, and another person loses the match. Ho thinks that a student is good enough to receive her school if the student is a of Taebo.
is a Korean word which means a person who is very good at games, sports, competitive programming, etc. In Taebo, Gosu has a different meaning.
Let's define a from player to player as a sequence of integers , where student has won student for all . We call as the of this winning path. For example, if there exists a of length 1, we can immediately know that has won student . If there exists a winning path of length 2, then may not win directly, but there exists some other player that has won, and has won .
The is defined as a minimum length of winning path from to , if such exists. There could be a case that can not find a winning path to . In that case, we define . Note that, the path can have zero length, thus is always .
Ho wants her student to be strong to all kind of opponents, so she defines the of student , as a maximum value among . A student is a in Taebo when the weakness of student is minimum among all weakness values. By this definition, there can be multiple Gosu-s.
Since Ho is too old to tell who is Gosu, your task is to find a Gosu and weakness value of Gosu to help Ho. If there exist multiple Gosu-s, you can print any of them.
输入格式
In the first line, the number of students is given.
In the -th line of next lines, a string consists of , , and . Let's denote -th character of as . is given as follows:
, if .
, if student won student .
, if student won student .
()
If , then or . ()
If , then . ()
If , then . ()
输出格式
Print two space-separated integers, and , where student is Gosu, and is weakness of student .
If there are multiple answers, you can print any of them.
