Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Sykli

Sykli


View task | Model solution | Statistics


Sykli

Time limit:1.00 s
Memory limit:128 MB

Annettuna on suunnattu verkko, ja tehtäväsi on selvittää, onko verkossa negatiivista sykliä. Jos verkossa on negatiivinen sykli, sinun tulee vielä tulostaa sen solmut.

Syöte

Syötteen alussa on kaksi kokonaislukua $n$ ja $m$: solmujen määrä ja kaarten määrä. Solmut on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden kaaren. Rivillä on kolme kokonaislukua $a$, $b$ ja $c$. Tämä tarkoittaa, että solmusta $a$ solmuun $b$ on kaari, jonka pituus on $c$.

Tuloste

Jos verkossa on negatiivinen sykli, tulosta ensin "10-4" ja sitten toiselle riville syklin solmut järjestyksessä jostain solmusta alkaen. Jos verkossa on useita negatiivisia syklejä, voit tulostaa minkä tahansa niistä.

Jos verkossa ei ole negatiivista sykliä, tulosta vain "QAQ".

Rajat
Esimerkki

Syöte:
4 5
1 2 1
2 4 1
3 1 1
4 1 -3
4 3 -2


Tuloste:
10-4
1 2 4 1