Fişierul intrare/ieşire:	aquapark.in, aquapark.out	Sursă	OJI 2018, Clasele 11-12
Autor	Zoltan Szabo	Adăugată de	Bogdan Ciobanu •bciobanu
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Aquapark

Pentru a atrage turiştii, primăria unui oraş a hotărât că va construi un parc acvatic imens cu n piscine. Parcul va avea o zonă acoperită şi va fi înconjurat de un spaţiu deschis pentru activităţi în aer liber.

Zona închisă va fi acoperită de o singură clădire de forma unui poligon, iar piscinele vor fi proiectate în vârfurile poligonului şi vor putea comunica între ele prin m căi de acces care nu se vor intersecta. Căile de acces între două piscine pot fi de tipul 1: canal umplut cu apă în interiorul clădirii, sau de tipul 2: o alee în afara clădirii.

În exemplul alăturat prin linie punctată se delimitează partea acoperită a parcului.
Avem 5 piscine, există 6 căi de acces: (1,2), (2,5), (1,4), (1,3), (3,4), (3,5), dintre care 2 sunt canale (tipul 1): (1,3) şi (1,4), respectiv 4 sunt alei (tipul 2): (1,2), (2,5), (3,4) şi (3,5).
Un alt proiect ce păstrează aceleaşi căi de acces, dar diferă prin tipul acestora, este să construim 4 canale: (1,2), (3,4), (3,5), (2,5) respectiv 2 alei: (1,3), (1,4).
În total putem construi 8 proiecte distincte cu aceste căi de acces. Două proiecte se consideră distincte dacă există cel puţin o cale de acces ce are tipuri diferite pe cele două proiecte.

Cerinţe

Cunoscând căile de acces între piscine, să se determine una dintre cerinţele următoare:

1. o modalitate de construire a căilor de acces, precizând tipul fiecăreia;
2. numărul proiectelor distincte.

Date de intrare

Fişierul de intrare aquapark.in conţine pe prima linie trei numerele separate prin câte un spaţiu c n m reprezentând în această ordine tipul cerinţei, numărul piscinelor respectiv numărul căilor de acces.
Următoarele m linii conţin câte două numere x şi y, reprezentând o cale de acces între piscina x şi piscina y.

Date de ieşire

Fişierul de ieşire aquapark.out va conţine în funcţie de valoarea lui c următoarele informaţii:

• dacă c=1: pe m linii se vor tipări câte trei numere separate prin câte un spaţiu x y t, semnificând că între piscina x şi piscina y există o cale de acces de tipul t (1-canal, 2-alee). Fiecare muchie citită din fişierul de intrare va trebui să apară exact o dată în fişierul de ieşire, indiferent de ordinea citirii.
• dacă c=2: se va tipări un singur număr ce va semnifica numărul proiectelor distincte modulo 666013.

Restricţii

• 1 ≤ n ≤ 70 000
• 1 ≤ m ≤ 100 000
• Între două piscine există cel puţin o cale de acces
• Nu există o cale de acces de la o piscină la ea însăşi
• Se asigură că pentru datele de test există cel puţin o soluţie,
• Dacă există mai multe soluţii se poate afişa oricare dintre acestea.
• Pentru teste în valoare de 16 puncte n,m ≤ 15
• Pentru alte teste în valoare de 49 de puncte n ≤ 1 000, m ≤ 1 500
• Conform regulamentului OJI, 10 puncte se vor acorda pe exemple.

Exemplu

Cum se trimit solutii?