신촌방위본부: 지하 벙커의 비밀

이 문제는 투 스텝 문제입니다. 채점 과정과 첫 번째 실행, 두 번째 실행을 꼼꼼히 읽고 문제를 파악하시기 바랍니다.

지난 2023년 2월 25일, 정체불명의 조직이 신촌방위본부 건물에 직접 타격을 가했다.

신촌방위본부 사령관은 화재로부터 많은 인원을 대피시켰지만, 건물들은 심각하게 파괴되었다.

신촌방위본부에는 $N$개의 건물과 건물들을 잇는 $N-1$개의 양방향 통로가 있다. 임의의 서로 다른 두 건물은 통로만 사용하여 오갈 수 있다. 또한 임의의 건물에 연결된 통로는 최대 $3$개뿐이다. 즉, 신촌방위본부의 건물과 통로는 정점의 차수가 $3$을 넘지 않는 트리 구조를 이룬다. 각 건물은 민트색 또는 보라색으로 칠해져 있다.

당신은 더 큰 위험에 대비하고자 하는 페인트공이다. 건물 중 정확히 한 곳에 지하 벙커가 있다. 당신은 폭격 속에서도 지하 벙커를 찾아갈 수 있도록 흔적을 남기기로 결심하였다.

당신은 최대 $\mathbf{30}$번, 건물의 색깔을 민트색에서 보라색으로, 또는 보라색에서 민트색으로 바꿀 수 있다.

2024년 2월 17일, 정체불명의 조직이 무차별 폭격을 가해 건물 간의 연결 관계와 건물의 색깔 외에는 아무것도 파악할 수 없는 폐허를 만들었다. 당신은 생존자들과 함께 지하 벙커로 이동해야 한다.

최대 $30$번의 색깔 변경으로 폭격 이후 상황에서 지하 벙커를 찾는 전략을 구상하여라.

시나리오 A

첫 번째 실행	두 번째 실행
예제 입출력 1의 첫 번째 테스트 케이스. 건물 2에 지하 벙커가 위치한 것을 알 수 있다. 건물 2와 건물 1의 색을 반전시키고 있다.	예제 입출력 2의 두 번째 테스트 케이스. 건물 번호가 $[1,2,3,4] \to [3,1,2,4]$로 새로 배정되었다. 새로 배정된 번호에 따라 건물 1에 지하 벙커가 위치한 것을 알 수 있다.

시나리오 B

첫 번째 실행	두 번째 실행
예제 입출력 1의 두 번째 테스트 케이스. 건물 5에 지하 벙커가 위치한 것을 알 수 있다. 건물 1, 건물 2, 건물 5, 건물 3의 색을 반전시키고 있다.	예제 입출력 2의 첫 번째 테스트 케이스. 건물 번호가 $[1,2,3,4,5] \to [4,1,5,2,3]$로 새로 배정되었다. 새로 배정된 번호에 따라 건물 3에 지하 벙커가 위치한 것을 알 수 있다.