Zły smok Bitol najechał krainę skrzatów i wziął w niewolę jej mieszkańców. Przydzielił każdemu z $n$ skrzatów inne stanowisko pracy i, samemu ległszy na stercie skradzionych kosztowności, jął leniwie nadzorować ich mozolne trudy.</p>

Jako że Bitol jest wyjątkowo gnuśnym smokiem, nie obserwuje jednocześnie wszystkich poddanych. Zamiast tego cały czas przygląda się uważnie tylko skrzatom pracującym przy pewnej grupie stanowisk. W tym czasie wszystkie nieobserwowane przezeń skrzaty mogą spotykać się oraz dowolnie zamieniać się miejscami (Bitol nie jest w stanie zapamiętać, przy którym stanowisku pracował który skrzat). Co godzinę smok obraca głowę i zaczyna obserwować inny podzbiór skrzatów.

Skrzat Bajtazyl, któremu smok przydzielił stanowisko $1$, chce zmobilizować towarzyszy niedoli do przeciwstawienia się Bitolowi. W tym celu musi najpierw spotkać się z sędziwym skrzatem Bajtomirem, któremu smok przydzielił stanowisko $n$. Przed Bajtazylem stoi zatem wyzwanie: odpowiednio zamieniając się z innymi skrzatami miejscami, winien jak najszybciej doprowadzić do sytuacji, w której on sam, ani stanowisko przy którym stoi aktualnie nasz śmiałek, ani stanowisko $n$ nie byłyby obserwowane przez smoka.

Twoim zadaniem jest ustalenie, kiedy najwcześniej może dojść do spotkania. Na szczęście wiadomo, że za $m$ godzin smok uśnie i wówczas wszystkie skrzaty będą w stanie komunikować się swobodnie.

입력 형식

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $n$ i $m$ ($1 ≤ n, m ≤ 1\,000\,000$) oznaczające odpowiednio liczbę skrzatów oraz liczbę godzin pozostałych do czasu, aż Bitol zaśnie. W następnych $m$ wierszach znajdują się opisy grup stanowisk obserwowanych przez smoka w kolejnych godzinach, po jednym w wierszu. Na opis $i$-tej grupy stanowisk składa się liczba całkowita $k_i$ ($1 ≤ k_i ≤ n$) oznaczająca liczbę obserwowanych stanowisk oraz $k_i$ uporządkowanych rosnąco liczb całkowitych ze zbioru ${1, \dots , n}$ oznaczających numery obserwowanych stanowisk. Wszystkie liczby w wierszu poodzielane są pojedynczymi odstępami.</p>

Możesz założyć, że $k_1 + k_2 + \dots + k_m ≤ 2\,000\,000$.

출력 형식

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą ze zbioru ${0, \dots ,m}$ - najmniejszą liczbę godzin, po której Bajtazyl może dotrzeć do Bajtomira.

예제 입력 1

5 4
3 1 3 4
2 3 5
3 1 2 3
2 1 2

예제 출력 1

2

예제 입력 2

6 2
4 2 3 4 5
6 1 2 3 4 5 6

예제 출력 2

0

예제 입력 3

10 4
1 1
2 9 10
7 1 3 4 7 8 9 10
2 1 10

예제 출력 3

4

힌트

Wyjaśnienie do przykładu:</p>

W pierwszym z powyższych przykładów podczas pierwszej godziny swej wyprawy Bajtazyl nie może opuścić stanowiska o numerze $1$, gdyż jest ono obserwowane przez smoka. Podczas drugiej godziny może on zamienić się miejscami ze skrzatem przy stanowisku o numerze $4$. Dzięki temu dopiero na początku trzeciej godziny smok Bitol odwróci głowę ku stanowiskom o numerach $1$, $2$, $3$, a Bajtazyl będzie mogł spotkać się z Bajtomirem.

W drugim z powyższych przykładów do spotkania może dojść natychmiast, gdyż w pierwszej godzinie smok nie patrzy na stanowiska Bajtazyla i Bitomira.

W trzecim przykładzie do spotkania może dojść dopiero wtedy, gdy Bitol uśnie.