Suç Baronunun Kaçışı#9888
Büyük bir suç örgütünün başındasınız. Saklanma yerleriniz, herhangi iki saklanma yeri arasında tam olarak bir yol bulunacak şekilde yer altı geçitleriyle birbirine bağlıdır. Karargahınız numaralı saklanma yerinde bulunmaktadır.
Polis, geçitleri birer birer kapatacaktır. Her kapatma işlemini önceden öğreniyorsunuz ve kalan geçitlerden geçmek için yeterli zamanınız oluyor. Hangi geçit kapatılırsa kapatılsın, her saklanma yerinin karargaha ulaşabilmesi için birkaç yeni geçit kazmak istiyorsunuz. Gerekli olan minimum yeni geçit sayısını bulun ve hangi geçitlerin kazılması gerektiğini belirtin.
İlk satırda iki tam sayı bulunur: n~(2 \le n \le 10^5) ve h~(0 \le h < n) — saklanma yeri sayısı ve karargahın bulunduğu saklanma yerinin numarası. Saklanma yerleri 'dan n - 1'e kadar numaralandırılmıştır.
Sonraki n - 1 satırın her birinde iki tam sayı ve b~(0 \le a, b < n) bulunur — bir geçitle birbirine bağlı saklanma yerlerinin numaraları.
İlk satırda bir tam sayı yazdırın — gereken minimum yeni geçit sayısı.
Sonraki satırın her birinde, yeni bir geçitle birbirine bağlanacak saklanma yerlerinin numaraları olan iki tam sayı ve yazdırın. Birden fazla çözüm varsa, herhangi birini yazdırabilirsiniz.
Örnek 1
Örnek 2