Minimum Day to Solve Problem K

You are given N problems numbered from 1 to N and a recommendation system that works over many days. Days are numbered from 0. On each day you may solve any number of problems, but you are only allowed to solve problems that have been previously recommended or that are recommended on the current day. Each problem can be solved at most once.

On day 0, the system initially recommends the first p problems (i.e. problems 1, 2, …, p).

For each problem i (where i > p), if it can possibly be recommended then it is associated with a set \(s_i\) (its prerequisites). The recommendation rule is as follows: Problem i will be recommended on day \(d+1\) if and only if all problems in \(s_i\) have been solved and at least one problem from \(s_i\) was solved on day \(d\.\)

You want to eventually solve problem K. Determine the minimum day by which you can accomplish this goal assuming you schedule your solving optimally.

Note: The key to unlocking a new recommendation is that when finishing all prerequisites for a problem, at least one of those prerequisites must be solved on the same day that the set is completed (i.e. the 'current' day). Even if all prerequisites have been solved in previous days, that will not trigger a recommendation.

Hint in terms of formulas:

For each problem i with \(s_i = \{u_1,u_2,\dots,u_m\}\), define the day it is solved as \(d(i)\). For the initially recommended problems (\(1 \le i \le p\)), we set \(d(i)=0\). For every other problem \(i\), you can achieve its solution on day

[ d(i)=\max{d(u): u\in s_i}+1, ]

since you can postpone the solving of one prerequisite to the day of finishing \(s_i\) so that the unlocking condition is satisfied. Output \(d(K)\).

inputFormat

The input begins with a line containing three integers N, p, and K (1 ≤ p ≤ N), where N is the total number of problems, p is the number of problems that are initially recommended, and K is the index of the target problem.

Then, for each problem i from p+1 to N (in order), there is a line describing its prerequisites. The line begins with an integer r (the number of problems in \(s_i\)), followed by r integers representing the indices of the prerequisite problems. It is guaranteed that the prerequisites for problem i are chosen among problems with indices less than i.

For problems 1 through p, no additional data is provided (they are initially recommended and have no prerequisites).

outputFormat

Output a single integer: the minimum day by which you can solve problem K under an optimal solving schedule.

sample

3 2 3
2 1 2

1