킹핀의 탈출

당신은 대규모 범죄 해커 네트워크의 킹핀이다. 전설에 따르면 당신보다 부유한 범죄자는 없었다고 한다. 가장 똑똑하기 때문만이 아니라, 가장 인색하기 때문이기도 하다.

경찰은 여러 해 동안 당신을 쫓아왔지만, 훌륭한 탈출 경로 덕분에 한 번도 잡지 못했다. 경찰이 당신의 여러 은신처 중 하나에서 당신을 잡으려 할 때마다, 당신은 터널과 뒷골목과 밀실로 이루어진 네트워크를 통해 재빨리 도망친다. 당신의 경로는 도시의 모든 은신처에서 다른 모든 은신처로 비밀 통로만 따라 이동할 수 있도록 구성되어 있다. 게다가 당신은 워낙 구두쇠라서 네트워크가 가능한 한 최소다. 모든 은신처 사이에 네트워크를 통과하는 경로가 정확히 하나뿐이다.

어제, 경찰 내부의 스파이가 불행한 사실을 알려주었다. 경찰이 당신을 눈치챘다는 것이다! 경찰은 당신의 비밀 네트워크를 알아냈고, 당신을 잡으려 할 것이다. 경찰은 탈출 경로 일부를 막고 당신을 현장에서 잡을 계획이다. 경찰은 당신이 더 이상 갈 곳이 없어질 때까지 비밀 통로를 하나씩 막기 시작할 것이다.

다행히 당신의 본부는 완전히 안전하다. 본부에 도착하기만 하면 항상 무사하다. 게다가 경찰 내부의 스파이가 경찰이 통로를 막기 시작하는 즉시 알려줄 수 있으므로, 경찰은 당신이 통보를 받기 전에 통로 하나만 막을 시간이 있다. 경찰이 더 많은 경로를 막기 전에 본부로 돌아가면 안전하다.

당신은 네트워크에 통로를 몇 개 추가해서, 그중 많아야 하나가 막혀도 다른 모든 은신처에서 본부로 갈 수 있게 하려 한다. 소식이 당신의 인색함을 바꾸지 않았으므로, 네트워크를 가능한 한 저렴하게 확장하려 한다. 추가해야 하는 통로의 최소 개수와 그 통로들이 무엇인지 알아낼 수 있겠는가?

• 입력은 네트워크의 은신처 수를 나타내는 정수 $2 \le n \le 10^5$와 본부의 위치를 나타내는 정수 $0 \le h < n$으로 시작한다.
• 이어서 $n - 1$개의 줄이 주어지며, 각 줄에는 위치 $a$와 위치 $b$ 사이에 탈출 경로가 있음을 나타내는 두 정수 $0 \le a, b < n$이 있다.

출력은 다음과 같다.

• 네트워크를 다시 안전하게 만들기 위해 추가해야 하는 탈출 경로의 최소 개수 $m$.
• 이어서 $m$개의 줄에 각각 두 정수 $0 \le a, b < n$을 출력한다. 이는 탈출 경로를 추가해야 하는 두 은신처를 나타낸다.