러시아의 많은 지역에서는 겨울 동안 눈이 내립니다. 러시아에는 $0$부터 $N-1$까지 번호가 매겨진 $N$개의 도시가 있습니다. 또한 $0$부터 $N-2$까지 번호가 매겨진 $N-1$개의 도로가 있습니다. 도로 $i$ ($0 \le i \le N-2$)는 서로 다른 두 도시 $A_i$와 $B_i$ ($0 \le A_i < B_i \le N-1$)를 양방향으로 연결합니다. 러시아의 서로 다른 두 도시 사이에는 몇 개의 도로를 차례로 거쳐 항상 이동할 수 있습니다.
각 도로의 적설 상태는 날마다 바뀝니다. 어느 날이든 각 도로는 눈이 쌓여 있거나 눈이 쌓여 있지 않은 상태 중 하나입니다. 하루 동안에는 도로의 적설 상태가 바뀌지 않습니다.
아냐(Anya)와 보리스(Boris)는 러시아 교통부에서 일합니다. 아냐는 도로 정보 관리 부서에서 일하고, 보리스는 시민들의 질문에 답하는 부서에서 일합니다. 시민의 질문은 다음과 같습니다: "수도인 도시 0에서 어떤 다른 도시로 이동하기 위해 반드시 지나야 하는 눈 덮인 도로의 최소 개수는 몇 개인가요?" 보리스는 보통 시민으로부터 질문을 받은 뒤 아냐와 연락하여 시민에게 답변합니다.
최근 러시아에서 $Q$일 동안 세계 프로그래밍 대회가 열리고 있습니다. 대회 기간에는 통신 회선이 혼잡해져 아냐와 보리스가 직접 연락하기 어려울 것으로 예상됩니다. 따라서 아냐와 보리스는 다음과 같은 방법으로 소통하기로 결정했습니다:
- 매일 아침, 아냐는 그날의 눈 덮인 도로 정보를 받아 중계 서버에 데이터를 보냅니다.
- 보리스는 시민으로부터 질문을 받으면 중계 서버와 통신하여 질문에 답합니다.
하지만 아냐와 보리스의 통신에는 다음과 같은 제약이 있습니다:
- 중계 서버의 용량은 $L = 1000$비트입니다. 아냐는 중계 서버에 최대 $L$비트의 정보를 저장할 수 있습니다.
- 중계 서버에 저장된 데이터는 매일 아침 모두 0으로 초기화됩니다.
- 보리스는 중계 서버와 한 번 상호작용하여 지정한 1비트의 정보를 읽을 수 있습니다.
- 하나의 질문에 답하기 위해 보리스는 질문당 최대 20번까지 중계 서버와 상호작용할 수 있습니다.
교통부 국장의 지인인 당신은 아냐와 보리스를 위한 전략을 고안해 달라는 부탁을 받았습니다.
시민들의 질문에 올바르게 답할 수 있는 아냐와 보리스의 전략을 구현하는 프로그램을 작성하세요.
구현 세부사항
동일한 프로그래밍 언어로 작성된 두 개의 파일을 제출해야 합니다.
첫 번째 파일의 이름은 Anya.c 또는 Anya.cpp입니다. 이 파일은 아냐의 전략을 구현하며, 다음 두 루틴을 구현해야 합니다. 프로그램은 Anyalib.h를 포함해야 합니다.
void InitAnya(int N, int A[], int B[])이 함수는 각 테스트 케이스마다 정확히 한 번 호출됩니다.- 인자
N은 도시의 수를 나타냅니다. - 인자
A[]와B[]는 길이가 $N-1$인 배열로, 도로의 연결 정보를 나타냅니다. 원소A[i]와B[i]($0 \le i \le N-2$)는 도로 $i$가 도시A[i]와B[i]를 양방향으로 연결함을 나타내는 정수이며, $0 \le A[i] < B[i] \le N-1$을 만족합니다.
- 인자
void Anya(int C[])이 함수는InitAnya가 호출된 후 $Q$번 호출됩니다. 이 함수는 하루가 시작될 때 눈 덮인 도로 정보가 갱신된 후 아냐가 중계 서버에 저장할 비트열을 결정하는 동작에 해당합니다.- 인자
C[]는 길이가 $N-1$인 배열로, 눈 덮인 도로 정보를 나타냅니다. 원소C[i]($0 \le i \le N-2$)는 0 또는 1인 정수이며,C[i] = 1은 도로 $i$에 눈이 쌓여 있음을 의미하고C[i] = 0은 도로 $i$에 눈이 쌓여 있지 않음을 의미합니다.
- 인자
함수 Anya 내부에서 다음 함수를 호출할 수 있습니다:
void Save(int place, int bit)이 함수는 아냐가 중계 서버에 비트를 저장하는 작업을 나타냅니다.- 인자
place는 비트를 기록할 위치를 나타냅니다.place는 $0$ 이상 $L-1$ 이하의 정수여야 합니다. 이 범위를 벗어난 값을 지정하면 Wrong Answer [1]로 판정됩니다. 또한 함수Anya의 각 호출에서 동일한place인자로 이 함수를 두 번 이상 호출할 수 없습니다. 동일한 인자로 두 번 호출하면 Wrong Answer [2]로 판정됩니다. - 인자
bit는 기록할 비트를 나타내는 정수로, 0 또는 1이어야 합니다. 그 외의 값을 지정하면 Wrong Answer [3]으로 판정됩니다.
- 인자
Save 호출 후 중계 서버의 place번째 비트 내용은 bit가 됩니다. 만약 Save 호출이 Wrong Answer로 판정되면 프로그램은 그 즉시 종료됩니다.
함수 Anya가 호출되기 직전에는 중계 서버의 비트들이 항상 모두 0으로 초기화됩니다. 즉, 함수 Anya가 종료될 때 Save 함수에 의해 저장 작업이 수행되지 않은 위치에는 0이 들어 있습니다.
두 번째 파일의 이름은 Boris.c 또는 Boris.cpp입니다. 이 파일은 보리스의 전략을 구현하며, 다음 두 루틴을 구현해야 합니다. 프로그램은 Borislib.h를 포함해야 합니다.
void InitBoris(int N, int A[], int B[])이 함수는 각 테스트 케이스마다 정확히 한 번 호출됩니다.- 인자
N은 도시의 수를 나타냅니다. - 인자
A[]와B[]는 길이가 $N-1$인 배열로, 도로의 연결 정보를 나타냅니다. 원소A[i]와B[i]($0 \le i \le N-2$)는 도로 $i$가 도시A[i]와B[i]를 양방향으로 연결함을 나타내는 정수이며, $0 \le A[i] < B[i] \le N-1$을 만족합니다.
- 인자
int Boris(int city)이 함수는InitBoris가 호출된 후 여러 번 호출됩니다. 이 함수는 시민의 질문에 대한 보리스의 응답 동작에 해당합니다.- 인자
city는 시민의 질문을 나타냅니다.city는 $1$ 이상 $N-1$ 이하의 정수입니다. 이는 시민이 도시 0에서city로 이동하기 위해 지나야 하는 눈 덮인 도로의 최소 개수를 묻는 것을 나타냅니다. - 함수
Boris는 시민의 질문에 대한 답으로 $0$ 이상 $N-1$ 이하의 정수를 반환해야 합니다. 이 범위를 벗어난 정수를 반환하면 Wrong Answer [4]로 판정됩니다. 답이 틀린 경우 Wrong Answer [7]로 판정됩니다.
- 인자
함수 Boris 내부에서 다음 함수를 호출할 수 있습니다:
int Ask(int place)이 함수는 보리스가 중계 서버에서 비트를 읽는 작업을 나타냅니다.- 인자
place는 비트를 읽을 위치를 나타냅니다.place는 $0$ 이상 $L-1$ 이하의 정수여야 합니다. 이 범위를 벗어난 값을 지정하면 Wrong Answer [5]로 판정됩니다.
함수
Ask의 반환값은 중계 서버의place번째 비트 내용을 나타내는 정수로, 0 또는 1입니다. 또한 함수Ask는 함수Boris의 각 호출에서 최대 20번까지 호출할 수 있습니다. 20번을 초과하여 호출하면 Wrong Answer [6]으로 판정됩니다.- 인자
만약 Ask 호출이 Wrong Answer로 판정되면 프로그램은 그 즉시 종료됩니다.
제한
- $2 \le N \le 500$.
- $1 \le Q \le 500$.
- $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
- $1 \le D_j$ ($1 \le j \le Q$).
- $D_1 + \dots + D_Q \le 500$.
- 서로 다른 임의의 두 도시 사이에는 몇 개의 도로를 차례로 거쳐 항상 이동할 수 있습니다.
서브태스크
- (15점) $N \le 20$.
- (5점) $N \le 100$.
- (35점) 모든 $0 \le i \le N-2$에 대하여 $A_i = i$이고 $B_i = i + 1$입니다.
- (45점) 추가 제한이 없습니다.
예제
입력 1
5 0 1 1 2 1 4 2 3 2 0101 3 2 4 3 1110 1 4
출력 1
1 0 2 2
참고
위의 예제는 상호작용 흐름을 보여줍니다. 입력의 첫 번째 줄은 $N=5$입니다. 다음 4개의 줄은 간선을 정의합니다. 다음 줄은 $Q=2$입니다. 이어지는 줄들은 각 날의 눈 덮인 도로 상태와 쿼리들을 설명합니다. 출력은 각 날의 쿼리들에 대해 보리스가 제공한 답을 보여줍니다.