JOI 주식회사의 공장에는 $0$부터 $N-1$까지 번호가 매겨진 $N$개의 작업대가 있다. 공장에는 $0$부터 $N-2$까지 번호가 매겨진 $N-1$개의 벨트 컨베이어가 있다. 벨트 컨베이어 $i$ ($0 \le i \le N-2$)는 작업대 $A_i$와 작업대 $B_i$를 연결한다. 이는 한 작업대에서 다른 작업대로 제품을 운반한다. 하지만 운반 방향은 눈으로 볼 수 없다. 벨트 컨베이어의 방향을 무시하면, 모든 작업대 쌍은 몇 개의 벨트 컨베이어를 통해 서로 연결되어 있다.

IOI 군은 이 공장의 공장장이다. 그는 모든 벨트 컨베이어의 운반 방향을 잊어버렸기 때문에, 다음과 같은 일련의 작업을 여러 번 수행하려고 한다.

1. 몇 개의 벨트 컨베이어를 골라, 선택한 벨트 컨베이어들의 운반 방향을 반대로 바꾼다.
2. 몇 개의 작업대를 골라, 선택한 각 작업대 위에 제품을 하나씩 놓는다.

3. 제품이 놓인 모든 작업대에 대해, 다음 중 하나가 동시에 일어난다.

   • 그 작업대에서 제품을 실어 나르는 벨트 컨베이어가 없다면, 아무 일도 일어나지 않는다.
   • 그 작업대에서 제품을 실어 나르는 벨트 컨베이어가 있다면, 작업대 위의 제품은 그러한 벨트 컨베이어 중 하나에 의해 운반된다. 제품은 그 벨트 컨베이어의 도착지 작업대에서 멈춘다. 제품은 그 이후로 더 이상 움직이지 않는다.

4. IOI 군은 각 작업대에 제품이 하나 이상 있는지 확인한다. 작업대에 제품이 있다면, IOI 군은 그 제품들을 모두 회수한다.

5. 작업 1.에서 방향을 바꾸었던 모든 벨트 컨베이어에 대해, IOI 군은 그 방향을 다시 되돌린다. 그 방향은 원래의 방향이 된다.

IOI 군은 위의 일련의 작업을 최대 $30$번 수행하여 모든 벨트 컨베이어의 원래 방향을 특정하고 싶어 한다.

벨트 컨베이어로 연결된 작업대들의 정보가 주어졌을 때, 위의 일련의 작업을 최대 $30$번 수행하여 모든 벨트 컨베이어의 원래 방향을 특정하는 IOI 군의 전략을 구현하는 프로그램을 작성하라.

구현 세부 사항

하나의 파일을 제출해야 한다.

제출할 파일의 이름은 conveyor.cpp이다. 이 파일은 다음 함수를 구현해야 한다. 프로그램은 전처리기 지시문 #include를 사용하여 conveyor.h를 포함해야 한다.

conveyor.cpp에는 다음 함수를 구현해야 한다.

• void Solve(int N, std::vector<int> A, std::vector<int> B)

  이 함수는 각 테스트 케이스마다 단 한 번 호출된다.

  • 매개변수 N은 작업대의 개수 $N$이다.
  • 매개변수 A, B는 벨트 컨베이어가 연결하는 작업대들을 나타내는 길이 $N-1$의 배열이다.

  프로그램은 다음 함수들을 호출할 수 있다.

  • std::vector<int> Query(std::vector<int> x, std::vector<int> y)

    이 함수를 사용하여 IOI 군은 공장에서 작업을 수행한다.

    • 매개변수 x는 길이 $N-1$의 배열이다. $0 \le i \le N-2$에 대해, x[i] = 1이면 IOI 군은 벨트 컨베이어 $i$의 방향을 반대로 바꾸고, x[i] = 0이면 벨트 컨베이어 $i$의 방향을 바꾸지 않는다.
    • 매개변수 y는 길이 $N$의 배열이다. $0 \le j \le N-1$에 대해, y[j] = 1이면 IOI 군은 작업대 $j$ 위에 제품을 놓고, y[j] = 0이면 작업대 $j$ 위에 제품을 놓지 않는다.
    • 이 함수의 반환값을 z라고 하자. 이는 길이 $N$의 배열이다. $0 \le j \le N-1$에 대해, z[j] = 1이면 작업대 $j$ 위에 하나 이상의 제품이 있는 것이고, z[j] = 0이면 작업대 $j$ 위에 제품이 없는 것이다.
    • 배열 x의 길이는 $N-1$과 같아야 한다. 이 조건을 만족하지 않으면 프로그램은 Wrong Answer [1]로 판정된다.
    • 배열 x의 모든 원소는 0 또는 1이어야 한다. 이 조건을 만족하지 않으면 프로그램은 Wrong Answer [2]로 판정된다.
    • 배열 y의 길이는 $N$과 같아야 한다. 이 조건을 만족하지 않으면 프로그램은 Wrong Answer [3]으로 판정된다.
    • 배열 y의 모든 원소는 0 또는 1이어야 한다. 이 조건을 만족하지 않으면 프로그램은 Wrong Answer [4]로 판정된다.
    • 함수 Query는 $30$번을 초과하여 호출할 수 없다. 만약 $30$번을 초과하여 호출하면 프로그램은 Wrong Answer [5]로 판정된다.

  • void Answer(std::vector<int> a)

    이 함수를 사용하여 IOI 군은 각 벨트 컨베이어의 원래 방향을 보고한다.

    • 매개변수 a는 길이 $N-1$의 배열이다. $0 \le i \le N-2$에 대해, 벨트 컨베이어 $i$가 $A_i$에서 $B_i$로 제품을 운반한다면 a[i] = 0이고, $B_i$에서 $A_i$로 제품을 운반한다면 a[i] = 1이다.
    • 배열 a의 길이는 $N-1$과 같아야 한다. 이 조건을 만족하지 않으면 프로그램은 Wrong Answer [6]으로 판정된다.
    • 배열 a의 모든 원소는 0 또는 1이어야 한다. 이 조건을 만족하지 않으면 프로그램은 Wrong Answer [7]로 판정된다.
    • IOI 군이 벨트 컨베이어의 방향을 잘못 보고하면 프로그램은 Wrong Answer [8]로 판정된다.
    • 함수 Answer는 정확히 한 번 호출되어야 한다. 함수 Answer가 두 번 이상 호출되면 프로그램은 Wrong Answer [9]로 판정된다. 함수 Solve가 종료될 때 함수 Answer가 호출되지 않았다면 프로그램은 Wrong Answer [10]으로 판정된다.

주의 사항

• 프로그램은 내부적인 용도로 다른 함수를 구현하거나 전역 변수를 사용할 수 있다.
• 프로그램은 표준 입력 및 표준 출력을 사용해서는 안 된다. 프로그램은 어떠한 방법으로도 다른 파일과 통신해서는 안 된다. 단, 표준 오류 출력으로 디버깅 정보를 출력하는 것은 허용된다.

컴파일 및 테스트 실행

대회 웹페이지에서 프로그램을 테스트할 수 있는 샘플 그레이더가 포함된 압축 파일을 다운로드할 수 있다. 이 압축 파일에는 프로그램의 샘플 소스 파일도 포함되어 있다.

샘플 그레이더는 grader.cpp 파일이다. 프로그램을 테스트하려면 grader.cpp, conveyor.cpp, conveyor.h를 같은 디렉터리에 두고 다음 명령을 실행하여 프로그램을 컴파일하라. 대신 압축 파일에 포함된 compile.sh를 실행해도 된다.

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

컴파일에 성공하면 실행 파일 grader가 생성된다.

실제 채점에 사용되는 그레이더는 샘플 그레이더와 다르다는 점에 유의하라. 샘플 그레이더는 단일 프로세스로 실행되며, 표준 입력에서 입력 데이터를 읽고 결과를 표준 출력으로 출력한다.

샘플 그레이더의 입력

샘플 그레이더는 표준 입력에서 다음 데이터를 읽는다.

$$ \begin{array}{llll} N \\ A_0 & A_1 & \cdots & A_{N-2} \\ B_0 & B_1 & \cdots & B_{N-2} \\ C_0 & C_1 & \cdots & C_{N-2} \end{array} $$

$0 \le i \le N-2$에 대해, 벨트 컨베이어 $i$가 작업대 $A_i$에서 작업대 $B_i$로 제품을 운반하면 $C_i=0$이고, 그렇지 않으면 $C_i=1$이다.

샘플 그레이더의 출력

샘플 그레이더는 표준 출력으로 다음 정보를 출력한다(따옴표는 명확성을 위한 것이다).

• 프로그램이 정답으로 판정되면, Query 함수의 호출 횟수를 “Accepted: 22”와 같이 보고한다.
• 프로그램이 어떤 종류든 오답(Wrong Answer)으로 판정되면, 샘플 그레이더는 그 종류를 “Wrong Answer [4]”와 같이 출력한다.

프로그램이 여러 종류의 오답 조건을 동시에 만족하는 경우, 샘플 그레이더는 그중 하나만 보고한다.

샘플 그레이더에서는 제품이 놓인 작업대에서 제품을 실어 나르는 벨트 컨베이어들 중 실제로 제품을 운반하는 벨트 컨베이어가 의사 난수에 의해 균등하고 무작위로 결정되며, 그 결과는 여러 번 실행해도 변하지 않는다. 의사 난수의 시드(seed)를 변경하려면 다음과 같이 첫 번째 정수 인자를 주어 샘플 그레이더를 실행하면 된다.

./grader 2023

채점 관련 참고 사항

일부 테스트 케이스에 대해 실제 그레이더는 적응형(adaptive)이다. 즉, 그레이더는 처음에 고정된 정답을 가지고 있지 않으며, 이전에 호출된 Query 함수에 따라 응답을 결정한다. 그레이더의 모든 응답과 모순되지 않는 정답이 적어도 하나 존재함이 보장된다.

제약 조건

모든 입력 데이터는 다음 조건을 만족한다.

• $0 \le A_i \le N-1$ ($0 \le i \le N-2$).
• $0 \le B_i \le N-1$ ($0 \le i \le N-2$).
• 벨트 컨베이어의 방향을 무시하면, 모든 작업대 쌍은 몇 개의 벨트 컨베이어를 통해 서로 연결되어 있다.

서브태스크

1. (1점) $N=2$.
2. (14점) $N=30$.
3. (10점) $N=100\,000$, $A_i=i$ ($0 \le i \le N-2$), $B_i=i+1$ ($0 \le i \le N-2$).
4. (75점) $N=100\,000$.

입출력 예제

다음은 샘플 그레이더를 위한 예제 입력과 그에 대응하는 함수 호출이다.

입력 1

3
0 2
2 1
1 0

함수 호출 예제

첫 번째 Query 함수 호출의 경우, [1, 0, 0] 외에 [0, 1, 0]도 가능한 반환값이다.

두 번째 Query 함수 호출의 경우, 작업대 $0$ 위의 제품은 벨트 컨베이어 $0$을 거쳐 작업대 $2$로 운반되어 그곳에서 멈춘다. 이 제품은 벨트 컨베이어 $1$을 거쳐 작업대 $1$로 운반되지 않는다는 점에 유의하라.

이 예제 입력은 어느 서브태스크의 제약 조건도 만족하지 않는다는 점에 유의하라.

대회 웹페이지에서 얻을 수 있는 파일들 중 sample-02.txt는 서브태스크 $1$의 제약 조건을 만족하며, sample-03.txt는 서브태스크 $2$의 제약 조건을 만족한다.