Nosaukums
Autosacīkstes 2 (auto2)
Laika limits
0.50s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

Autosacīkstēs piedalās N automašīnas, kas sanumurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Automašīnas pa šauru ceļu joņo viena aiz otras, veikdamas apdzīšanas retajās vietās, kur tas ir iespējams. “Apdzīšana” nozīmē, ka viena automašīna, kas atradās tieši aiz citas, aizbrauca tai garām - katras apdzīšanas rezultātā tieši divas blakus mašīnas samainās vietām.

Ferdinands ir nokavējis sacīkšu sākumu un tagad ar interesi seko sacīkstēm, pierakstot visas apdzīšanas pēc kārtas. Kāda ir bijusi automašīnu secība, pirms Ferdinands sācis veikt pierakstus, nav zināms.

Piemēram, ja N=4, 1. auto apdzinis 4. un 2. auto apdzinis 4., tad iespējamās divas automašīnu secības pēc šīm apdzīšanām ir 

Diemžēl, savos pierakstos Ferdinands var būt kļūdījies un kādu apdzīšanu izlaidis vai ierakstījis nepareizi.

Piemēram, ja N=5 un ierakstīts, ka 2. auto apdzinis 3. un 3. auto apdzinis 4., tad šīs apdzīšanas nevar sekot tieši viena aiz otras -- pēc pirmās apdzīšanas 3. auto atrodas tieši aiz 2. auto un nevar apdzīt 4. auto. Tātad šajā gadījumā nav iespējama neviena automašīnu secība.

Uzrakstiet programmu, kas aprēķina dažādo iespējamo automašīnu secību pēc Ferdinanda novērotajām apdzīšanām!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dotas naturālu skaitļu N (automašīnu skaits, N ≤ 105) un A (pierakstīto apdzīšanu skaits, A ≤ 105) vērtības, kas atdalītas ar tukšumzīmi. Ievaddatu nākamajās A rindās doti apdzīšanu apraksti tādā secībā, kā tās pierakstījis Ferdinands. Katru apdzīšanu apraksta divi atšķirīgi naturāli skaitļi robežās no 1 līdz N, kas atdalīti ar tukšumzīmi. Pirmais skaitlis ir tās automašīnas numurs, kas veica apdzīšanu, bet otrais - tās mašīnas numurs, kas tika apdzīta.


Izvaddatu raksturojums

Vienīgajā rindā jāizvada vesels nenegatīvs skaitlis - dažādo iespējamo automašīnu secību pēc Ferdinanda novērotajām apdzīšanām skaits pēc moduļa 109+9.


Piezīmes

Uzdevums no Latvijas 31. Informātikas olimpiādes.


Paraugdati

Stdin
4 2
1 4
2 4
Stdout
2

Stdin
5 2
2 3
3 4
Stdout
0

Stdin
100 1
100 1
Stdout
863172927

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.