31426번 - 신촌방위본부: 지하 벙커의 비밀 투 스텝

문제

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

지난 2023년 2월 25일, 정체불명의 조직은 신촌방위본부 건물에 직접 타격을 실시하였다.

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

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

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

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

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

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

채점 과정

여러분의 프로그램은 채점 데이터 하나당 총 두 번 실행된다. 당신은 하나의 소스 코드에 두 가지 실행 과정을 모두 구현해야 한다.

채점 과정 이해를 돕는 순서도. 자세한 내용은 아래 서술을 참고하라.

• 첫 번째 실행_{폭격 이전을 나타냄}
  • 여러분의 프로그램은 신촌방위본부의 구조와 지하 벙커가 위치한 건물 번호를 입력받는다.
  • 여러분의 프로그램은 최대 30ドル$번의 색상 변경 정보를 출력하고 종료해야 한다.
• 채점 프로그램의 작업
  • 출력이 올바르지 않다면 틀렸습니다 판정을 내리고 종료한다.
  • 테스트 케이스별로,
    • 색상 변경을 반영한다.
    • 건물 번호를 일괄적으로 섞는다.
    • 통로의 입력 순서를 섞는다.
    • 통로가 잇는 두 건물의 입력 순서도 각각 섞는다.
  • 테스트 케이스의 순서를 섞는다.
  • 섞는 모든 과정은 비적응적이다.
• 두 번째 실행_{폭격 이후를 나타냄}
  • 여러분의 프로그램은 신촌방위본부의 구조를 입력받는다.
  • 여러분의 프로그램은 지하 벙커가 위치한 건물 번호를 출력하고 종료해야 한다. 새로 배정된 번호를 기준으로 출력하면 된다.
• 채점 프로그램의 작업
  • 출력이 올바르지 않거나 지하 벙커가 위치한 건물 번호를 맞히지 못했다면, 틀렸습니다 판정을 내리고 종료한다.

첫 번째 실행

입력

첫 번째 줄에 문자열 first가 있다.

두 번째 줄에 테스트 케이스의 수 $T$가 주어진다. 다음 줄부터 $T$개의 각 테스트 케이스가 주어진다. $(1\le T\le 100)$

테스트 케이스의 구성은 다음과 같다.

• 첫 번째 줄에 건물의 개수 $N$과 지하 벙커가 있는 건물의 번호 $M_1$이 공백으로 구분되어 주어진다. $(1\le N\le 10^6;$ 1ドル\le M_1\le N)$
• 두 번째 줄에는 건물 색깔을 나타내는 $C_1,C_2,\ldots,C_N$이 공백으로 구분되어 주어진다. 건물 $i$에 대해 $C_i=0$이라면 민트색, $C_i=1$이라면 보라색으로 칠해져 있음을 의미한다.
• 이어서 $N-1$개의 줄에 $j$번째 통로를 나타내는 두 정수 $U_j, V_j$가 공백으로 구분되어 주어진다. 통로가 이루는 그래프는 트리임이 보장된다. $(1\le U_j,V_j\le N;$ $U_j\neq V_j)$

모든 테스트 케이스의 $N$ 총합은 10ドル^6$을 넘지 않는다.

출력

$T$개의 각 테스트 케이스에 대해 첫 번째 줄에는 색깔 반전을 할 횟수 $K$를, 두 번째 줄에는 색깔 반전을 할 건물 번호를 나타내는 $B_1,B_2,\ldots,B_K$를 공백으로 구분하여 출력한다. 한 건물의 색을 여러 번 바꾸는 것도 가능하다. $(0\le K\le 30;$ 1ドル\le B_i\le N)$

두 번째 실행

입력

첫 번째 줄에 문자열 second가 있다.

두 번째 줄에 테스트 케이스의 수 $T$가 주어진다. 다음 줄부터 $T$개의 각 테스트 케이스가 주어진다. $(1\le T\le 100)$

테스트 케이스의 구성은 다음과 같다.

• 첫 번째 줄에 건물의 개수 $N$이 주어진다. $(1\le N\le 10^6)$
• 두 번째 줄에는 건물 색깔을 나타내는 $C_1,C_2,\ldots,C_N$이 공백으로 구분되어 주어진다. 건물 $i$에 대해 $C_i=0$이라면 민트색, $C_i=1$이라면 보라색으로 칠해져 있음을 의미한다.
• 이어서 $N-1$개의 줄에 통로 $j$를 나타내는 두 정수 $U_j,ドル $V_j$가 공백으로 구분되어 주어진다. 통로가 이루는 그래프는 트리임이 보장된다. $(1\le U_j,V_j\le N;$ $U_j\neq V_j)$

모든 테스트 케이스의 $N$ 총합은 10ドル^6$을 넘지 않는다.

출력

$T$개의 각 테스트 케이스에 대해 알아낸 지하 벙커가 있는 건물의 새로 부여된 번호 $M_2$를 출력한다. $(1\le M_2\le N)$

입력

출력

제한

힌트

시나리오 A

시나리오 B