CSES - 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 nn ja mm: solmujen määrä ja kaarten määrä. Solmut on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, joista jokainen kuvaa yhden kaaren. Rivillä on kolme kokonaislukua aa, bb ja cc. Tämä tarkoittaa, että solmusta aa solmuun bb on kaari, jonka pituus on cc.

Voit olettaa, että jokainen kaari alkaa ja päättyy eri solmussa.

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

  • 1n25001 \le n \le 2500
  • 1m50001 \le m \le 5000
  • 1a,bn1 \le a,b \le n
  • 109c109-10^9 \le c \le 10^9

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