34220번 - 그래프 리뷰 유튜버 스페셜 저지

도훈이는 많은 구독자를 보유한 그래프 리뷰 채널을 운영하고 있다.

도훈이는 최소 채색수^*만을 이용하여 색칠된 그래프만을 리뷰해야 한다는 본인만의 철학에 따라, 최근 방송에서 최소 채색수인 $2$가지 색으로만 색칠된 트리^†를 리뷰하였으나 정치색 논란에 휩싸이게 되었다.

정치색 논란에 휩싸이지 않기 위해서 그래프는 적어도 $4$가지 색을 이용하여 색칠되어 있어야 한다.

도훈이를 도와, 트리에 간선을 최소 개수로 추가해 최소 채색수를 $4$ 이상으로 만들어라. 단, 추가할 간선이 잇는 두 정점은 서로 달라야 한다.

^* 최소 채색수는 임의의 간선이 잇는 두 정점의 색이 다르도록 모든 정점에 색을 배정하기 위해 필요한 색깔의 최소 가짓수이다. ^† 트리는 $N$개의 정점과 $N-1$개의 간선으로 이루어진 무방향 연결 그래프이다.

첫째 줄에 정점의 개수 $N$이 주어진다. $(4\le N\le 100\,000)$

이어서 $N-1$개의 각 줄에는 트리의 $i$번째 간선이 잇는 두 정점 $u_i$, $v_i$가 공백으로 구분되어 주어진다.

첫째 줄에 추가할 간선의 최소 개수 $K$를 출력한다. $(0\le K)$

이어서 $K$개의 각 줄에 추가할 $i$번째 간선이 이을 서로 다른 두 정점 $u_i$, $v_i$를 공백으로 구분하여 출력한다.

가능한 답이 여러 가지라면, 그중 아무것이나 출력한다.