철도

시간 제한1초메모리 제한1024 MB

요약

트리에 가짜 간선 K개를 추가하고 노드 하나에 표시를 남기는 함수와, 변형된 그래프에서 원래 트리를 복원하는 함수를 작성합니다.

문제

사이가 나쁜 A나라와 B나라가 있다. A나라는 B나라를 침략하려고 B나라의 철도망을 알아내려 한다. A나라는 B나라에 여러 차례 스파이를 보냈지만, 스파이는 의미 있는 정보를 캐내기 전에 항상 잡혔다. 그래서 A나라가 아는 정보는 다음이 전부이다.

A나라는 스파이를 보내는 방법에 한계가 있음을 깨닫고, B나라 철도회사의 고위 간부를 매수해 철도망 그림을 얻으려 한다. 그림을 그대로 보내면 배신자가 드러나므로, 배신자는 그림을 다음과 같이 고쳐서 A나라에 보낸다.

그림에 $K$ 개의 가짜 철로를 그린다. 철로로 직접 연결되지 않은 서로 다른 두 역 $a$ 와 $b$ 를 골라 가짜 철로로 직접 잇는 과정을 $K$ 번 반복한다.
역 하나에 특별한 표시를 한다.
마지막으로 모든 역의 번호를 지운다.

배신자가 보낸 최종 그림만으로는 B나라의 철도망인지 알기 어렵다. 따라서 비밀 정보가 유출되었다는 사실을 아무도 모를 것이다.

이 계획이 성공하려면 다음 문제를 해결해야 한다.

A나라가 받은 그림에는 역 번호가 없고, 어느 철로가 진짜이고 어느 철로가 가짜인지도 표시되어 있지 않다. A나라가 아는 것은 특별한 표시가 있는 역과, 가짜 철로를 $K$ 개 놓았다는 사실뿐이다.
따라서 보내는 쪽은 받는 쪽이 그림만 보고 진짜 철로와 가짜 철로를 구별할 수 있도록, 적절한 위치에 가짜 철로를 놓고 적절한 역에 특별한 표시를 해야 한다.
받는 쪽은 보내는 쪽이 그림을 고친 방법을 이해하고, 받은 그림에서 원래 철도망 그림을 구해야 한다.

위에서 설명한 것처럼, 철도망 그림을 고치는 함수와 고쳐진 그림에서 진짜 철도망을 구하는 함수, 두 함수가 필요하다. A나라는 여러분에게 이 일을 맡기려고 한다.

시간 제한: 1000 ms, 메모리 제한: 1024 MB.