- Time limit: 1.00 s
- Memory limit: 512 MB
Bittimaassa on kaupunkia, joiden välillä on tietä. Minkä tahansa kahden kaupungin välillä on olemassa reitti.
Haluat perustaa joihinkin kaupunkeihin toimiston, mutta rajoituksena on, että jokaisen kahden toimiston etäisyys tulee olla vähintään .
Mikä on suurin määrä toimistoja, jotka voit perustaa?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : kaupunkien määrä ja pienin sallittu etäisyys. Kaupungit on numeroitu .
Sitten syötteessä on riviä, jotka kuvaavat tiet. Jokaisella rivillä on kaksi kokonaislukua ja : kaupunkien ja välillä on tie.
Tuloste
Tulosta ensin yksi kokonaisluku: suurin toimistojen määrä .
Tulosta sitten lukua: kaupungit, joihin toimistot perustetaan. Voit tulostaa minkä tahansa kelvollisen ratkaisun.
Rajat
Esimerkki
Syöte:
5 3 1 2 2 3 3 4 3 5
Tuloste:
2 1 4
Selitys: Voit perustaa korkeintaan kaksi toimistoa. Yksi ratkaisu on perustaa toimistot kaupunkeihin ja .