CSES - Molekyyli
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Tutkiessaan Uolevin DNA:ta tutkijat löysivät myös kaksi erikoista molekyyliä. Kummassakin molekyylissä on nn atomia, joista yksi on uraaniatomi ja muut ovat happiatomeita. Lisäksi atomien välillä on n1n-1 sidosta ja kaikki atomit ovat jotain kautta yhteydessä toisiinsa.

Tutkijat eivät päässeet kuitenkaan selvyyteen, onko kyseessä kaksi aidosti erilaista molekyyliä, vai onko niiden rakenne samanlainen. Molekyylien rakenne on samanlainen, jos ne näyttävät piirrettynä samoilta, kunhan atomien sijainnit valitaan sopivasti. Voisitko auttaa tutkijoita?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: atomien määrä molekyylissä. Atomit on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n, ja atomi 1 on uraani.

Sitten syötteessä on n1n-1 riviä, jotka kuvaavat ensimmäisen molekyylin. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: kaksi atomia, joiden välillä on sidos molekyylissä.

Lopuksi syötteessä on n1n-1 riviä, jotka kuvaavat toisen molekyylin vastaavalla tavalla.

Tuloste

Ohjelmasi tulee tulostaa 10-4, jos molekyylit ovat samanlaiset, ja muuten QAQ.

Rajat

  • 2n1052\leq n\leq 10^5

Esimerkki

Syöte:

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

Tuloste:

10-4