Farmer John's N cows (1 \leq N \leq 10^5), numbered 1 \ldots N as always, happen to have too much time on their hooves. As a result, they have worked out a complex social hierarchy related to the order in which Farmer John milks them every morning.

After weeks of study, Farmer John has made M observations about his cows' social structure (1 \leq M \leq 50,000). Each observation is an ordered list of some of his cows, indicating that these cows should be milked in the same order in which they appear in this list. For example, if one of Farmer John's observations is the list 2, 5, 1, Farmer John should milk cow 2 sometime before he milks cow 5, who should be milked sometime before he milks cow 1.

Farmer John's observations are prioritized, so his goal is to maximize the value of X for which his milking order meets the conditions outlined in the first X observations. If multiple milking orders satisfy these first X conditions, Farmer John believes that it is a longstanding tradition that cows with lower numbers outrank those with higher numbers, so he would like to milk the lowest-numbered cows first. More formally, if multiple milking orders satisfy these conditions, Farmer John would like to use the lexicographically smallest one. An ordering x is lexicographically smaller than an ordering y if for some j, x_i = y_i for all i < j and x_j < y_j (in other words, the two orderings are identical up to a certain point, at which x is smaller than y).

Please help Farmer John determine the best order in which to milk his cows.

Problem credits: Jay Leeds

#4073 upload 4 done 3 how_to_reg 3

Milking Order timer 2s memory 512MB

#4073

Milking Order 2s 512MB