The annual sailing race is organized on a round shape lake. There are N harbors, numbered from 1 to N around the lake counterclockwise. The race consists of several stages, where each stage runs on a straight line from one harbor to another, and the race track can only meet a harbor at most once. The organizers want to create a race track that contains the highest possible number of stages.

They must keep in mind that a sailboat at a given harbor may only go to some specific harbors on a direct route. Fortunately, for each harbor A they have the list of direct destinations from A, i.e. a list of other harbors to which a sailboat can go on a straight line from A. Generally, the race track consists of non-intersecting stages, to avoid the collision of sailboats. This year, however, a new technology is available, with which one crossing may be allowed if it lies on the first stage. So if the race track starts at harbor S and the next harbor in the track is T then at most one stage can cross the first stage S-T. The organizers may decide to allow a crossing like this, or rather choose the classical design with non-intersecting stages.

Task

입력

• The first line of the input contains two integers, the first number N (1 ≤ N ≤ 500) is the number of harbors and the second number k is the type of the required race track. If k is 0 then a classical track (without crossings) is required, while if k is 1 then the track may contain at most one crossing, as specified above.
• The next N lines contain the list of direct destinations from the harbors. The (i+1)th line contains the list for harbor i, a space-separated list of integers, terminated by 0.

출력

• The first line of the output contains one integer M, the maximal number of stages that a race track of the given type can contain.
• The second line contains the identifier number of the starting harbor of one such race track.

If there are multiple solutions, your program should output only one; it does not matter which one.

입출력 예

입력

7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0

출력

5
2

출처:ceoi 2012