CSES - Toimistot
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Bittimaassa on nn kaupunkia, joiden välillä on n1n-1 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 dd.

Mikä on suurin määrä toimistoja, jotka voit perustaa?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja dd: kaupunkien määrä ja pienin sallittu etäisyys. Kaupungit on numeroitu 1,2,,n1,2,\dots,n.

Sitten syötteessä on n1n-1 riviä, jotka kuvaavat tiet. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: kaupunkien aa ja bb välillä on tie.

Tuloste

Tulosta ensin yksi kokonaisluku: suurin toimistojen määrä kk.

Tulosta sitten kk lukua: kaupungit, joihin toimistot perustetaan. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

  • 1n,d21051 \le n,d \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n

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 11 ja 44.