3304번 - Sailing Race 스페셜 저지다국어

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.

You are to write a program that computes a race track of the given type containing the highest possible number of stages.

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.