MOG
Spanish
|
English

Matcom Online Grader

Latin American Regional Contest - 2018

Ended

F - Fantastic Beasts

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

The eccentric magizoologist Newt Scamander recently came to Nlogonia to study the fantastic creatures that inhabit this prosperous kingdom. But before he could begin to explore the area an accident disrupted his plans: his suitcase sprang open and his collection of fantastic beasts escaped from the magical object.

The inhabitants of Nlogonia love zoos, and so there are many of them in the kingdom. It turns out that the beasts share Nlogonians’ passion for zoos and since the accident they have been visiting the various zoos.

Beasts breaking free and causing trouble is nothing new for Newt so he had trackers put on the beasts since the previous incident. Thus, at any moment he knows the exact position of each of the beasts. After watching the beasts movements for some time he noticed that they follow a peculiar pattern: if a beast is currently in a given zoo, after a unit of time it will either stay in that zoo or it will move to another zoo that depends on the current zoo. All beasts that move to another zoo do this instantly and simultaneously.

With this information Newt conjectured that perhaps it’s not so difficult to recover the creatures. He believes that eventually all of them may meet in the same zoo at the same time so he only needs to wait at the right place and capture all the fantastic beasts at once. Given the information Newt has so far, can you help him determine where and when to wait for the beasts? If there are several possibilities, he wants to catch the beasts as early as possible.

Input

The first line contains two integers $B$ ($1 \leq B \leq 10$) and $Z$ ($1 \leq Z \leq 100$), indicating respectively the number of fantastic beasts and the number of zoos. Zoos are identified by distinct integers from $1$ to $Z$. Each of the next $B$ lines describes Newt's findings on a different beast with $Z+1$ integers $P_0, P_1, ..., P_Z$ ($1 \leq P_i \leq Z$ for $i = 0, 1, ..., Z$); the value $P_0$ is the zoo where the beast initially is, while for $i = 1, 2, ..., Z$ the value $P_i$ is the zoo where the beast would be after a unit of time if it is currently in the zoo $i$.

Output

Output a single line with two integers, $P$ and $T$, indicating that all the beasts will meet for the first time at zoo $P$ after $T$ units of time, or the character “*” (asterisk) if the beasts will never be all at the same zoo.

Sample test(s)

Input
2 4 3 4 1 2 3 2 1 1 4 3
Output
1 2
Input
2 4 3 4 1 2 3 4 1 1 4 3
Output
*