Bybana

문제

Kollektivtrafiken i Stackköping utgörs av en bybana med $NN$ stationer och $MM$ linjer. Varje linje består av en ordnad sekvens av stationer där det går att åka i båda riktningarna. En resa på bybanan är en förflyttning mellan två stationer på en och samma linje. Om linjen exempelvis består av stationerna $(3,7,5,2,1,9)(3,7,5,2,1,9)$ så kommer en resa från $11$ till $55$ att åka förbi stationerna $11$, $22$, $55$.

Ett vanligt hälsoproblem i Stackköping är att folk åker korta sträckor på bybanan istället för att gå. För att motverka detta har kommunen beslutat att byta till ett nytt betalsystem där priset för en resa är proportionellt mot slöseriet. Slöseriet för en resa definieras som antalet stationer på linjen som bybanan inte åkte förbi. I exemplet ovan så är slöseriet $33$, eftersom stationerna $3,7,93,7,9$ inte åktes förbi.

Du vill ta dig från station $11$ till station $NN$ genom en sekvens av resor. Vad är det minsta möjliga totala slöseriet? Det är garanterat att det går att ta sig till alla stationer.

입력

Den första raden av indata innehåller två heltal $NN$ och $LL$ ($2\le N,L\le {10}^{5}2\; \backslash le\; N,L\; \backslash le\; 10^5$): antalet stationer respektive antalet linjer i bybanenätverket. Därefter följer $LL$ rader som var och en beskriver en linje. En linje beskrivs av ett tal $MM$ ($2\le M\le N2\; \backslash le\; M\; \backslash le\; N$) följt av $MM$ tal mellan $11$ och $NN$: antalet stationer på linjen respektive stationerna på linjen. Dessa $MM$ tal är garanterat distinkta.

Låt $SS$ vara summan av $MM$ över alla linjer. Det garanteras att $S\le 3\cdot {10}^{5}S\; \backslash le\; 3\backslash cdot\; 10^5$.

출력

Skriv ut ett tal: det minsta möjliga totala slöseriet för en färd från station $11$ till station $NN$.

힌트

I det första exemplet kan vi först resa från $11$ till $22$ på den första linjen. Sedan kan vi resa från $22$ till $66$ på den andra linjen. Slöseriet för resorna är $11$ respektive $22$, så svaret är $33$.

I det andra exemplet kan vi börja med att resa från $11$ till $44$, med slöseriet $11$. Därefter kan vi resa från $44$ till $55$ vilket bidrar med $00$ slöseri eftersom alla stationer besöks på sträckan.

6 2
3 1 2 3
4 4 2 6 5

3

5 1
5 5 1 2 3 4

1