Sailing Race
Time limit3sMemory limit32 MB
Find the longest simple path on a circular arrangement of harbors using directed edges so that chords never cross except possibly one crossing involving the first stage, and report the max length with smallest starting harbor.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Geometry, Graph
- Solved
- No attempts yet
Problem
An annual sailing race is held on a circular lake. There are N harbors, numbered 1 to N counterclockwise around the shore.
A race track is a route that visits a sequence of distinct harbors; no harbor may be visited twice. Each consecutive pair of harbors in the route is one stage, sailed along the straight segment (chord) that joins them. The number of stages is therefore one less than the number of visited harbors.
A sailboat cannot sail directly between every pair of harbors. For each harbor A you are given the list of harbors that are directly reachable from A, i.e. the harbors to which a boat can sail in a straight line starting at A.
Because every stage is a straight chord, two stages may geometrically cross each other. To avoid collisions the stages must normally be pairwise non-crossing. (Two stages that merely share a harbor as a common endpoint are not considered to cross.)
This year a new technology permits at most one crossing, but only if it involves the very first stage. Concretely, if the route starts at harbor S and its first stage goes to harbor T, then at most one other stage may cross the segment S–T, and no other pair of stages may cross at all. The organizers may either use this single-crossing allowance or keep the classical, fully non-crossing design.
Determine a race track of the required type that has the greatest possible number of stages.
Input
The first line contains two integers N and k (1 ≤ N ≤ 500). N is the number of harbors. k selects the required design: if k = 0 the track must be classical (no crossings at all); if k = 1 the track may contain at most one crossing, and that crossing must involve the first stage as described above.
Each of the next N lines describes the direct destinations of one harbor. Line i + 1 lists the harbors directly reachable from harbor i: zero or more space-separated integers, terminated by a single 0.
Output
Print two lines.
The first line contains M, the maximum number of stages that a race track of the required type can have.
The second line contains the smallest starting-harbor number among all race tracks that attain M stages. If M = 0 (no stage is possible), print 1.
Hint
The figure illustrates one optimal race track for the example.
