Fuga del Boss#9888
Sei il capo di una grande organizzazione criminale. I tuoi rifugi sono collegati da passaggi sotterranei in modo tale che esiste esattamente un percorso tra due rifugi qualsiasi. Il tuo quartier generale si trova nel rifugio .
La polizia bloccherà i passaggi uno alla volta. Vieni a conoscenza di ogni blocco in anticipo e hai abbastanza tempo per spostarti attraverso i passaggi rimanenti. Vuoi scavare diversi nuovi passaggi in modo che, qualunque sia il singolo passaggio bloccato, ogni rifugio possa comunque raggiungere il quartier generale. Trova il numero minimo di nuovi passaggi e specifica quali passaggi devono essere scavati.
La prima riga contiene due interi n~(2 \le n \le 10^5) e h~(0 \le h < n) — il numero di rifugi e il numero del rifugio dove si trova il quartier generale. I rifugi sono numerati da a n - 1.
Ciascuna delle successive n - 1 righe contiene due interi e b~(0 \le a, b < n) — i numeri dei rifugi collegati da un passaggio.
Nella prima riga stampa un intero — il numero minimo di nuovi passaggi.
In ciascuna delle successive righe stampa due interi e — i numeri dei rifugi da collegare con un nuovo passaggio. Se esistono più soluzioni, stampane una qualsiasi.
Esempio 1
Esempio 2