P10123 [USACO18OPEN] Milking Order B

Farmer John’s $N$ cows ($2\le N\le 100$), conveniently numbered $1\ldots N$, have been feeling bored. So, they have developed a complex social structure related to the order they line up in each morning when Farmer John milks them. After several weeks of study, Farmer John has found that this structure is based on two key properties. First, because of the cows’ social ranks, some cows insist on being milked before other cows, based on their rank. For example, if cow $3$ has the highest rank, cow $2$ is in the middle, and cow $5$ is low-ranked, then cow $3$ must be milked first, then cow $2$, and finally cow $5$. Second, some cows will only allow themselves to be milked at a specific position in the line. For example, cow $4$ might insist on being the second cow to be milked out of all the cows. Fortunately, Farmer John can always milk his cows in an order that satisfies all of these conditions. Unfortunately, cow $1$ has recently become sick, so Farmer John wants to milk her as early as possible, so she can return to the barn for some much-needed rest. Please help Farmer John determine the earliest possible position where cow $1$ can appear in the milking order.

The first line contains $N$, $M$ ($1\le M

Output the earliest possible position where cow $1$ can appear in the milking order.

In this example, Farmer John has six cows, and cow $1$ is sick. His milking order must have cow $4$ before cow $5$, and cow $5$ before cow $6$. Also, Farmer John must milk cow $3$ first, and cow $5$ third. Since FJ must milk cow $3$ first, and because cow $4$ must be before cow $5$, cow $4$ has to be milked second, and then cow $5$ third. Therefore, the earliest possible position for cow $1$ in the milking order is fourth. Translated by ChatGPT 5