간선 소매넣기

※ 현재 DOJ의 함수 구현 투스텝 문제는 C++17만 지원합니다. 반드시 C++17로 제출해야 합니다.

이 문제는 투스텝 문제이다.

유담이는 다다스에게 간선 하나를 몰래 전달하려고 한다.

유담이 역할의 프로세스는 정점이 $N$개인 단순 연결 무향 그래프 $G$와 $G$에 존재하지 않는 간선 $e^*$를 받는다. 유담이는 $e^*$를 $G$에 추가한 뒤, 얻은 그래프의 모든 간선에 방향을 하나씩 부여해야 한다.

채점기는 유담이가 반환한 방향을 적용한다. 그 후 정점 번호와 간선 번호를 각각 임의로 다시 매긴다. 다다스 역할의 새로운 프로세스는 이렇게 만들어진 단순 연결 유향 그래프만 받는다. 다다스는 정점과 간선의 원래 번호를 알 수 없다.

다다스는 유담이가 추가한 간선의 현재 번호를 반환해야 한다.

두 프로세스 사이에 메모리, 파일, 전역 변수 등의 상태는 공유되지 않는다. 유담이가 다다스에게 전달할 수 있는 정보는 방향이 부여된 그래프뿐이다. 정점과 간선의 번호가 어떻게 다시 매겨지더라도 항상 성공해야 한다.

제공된 헤더를 #include "edgesmuggling.h"로 포함하고, yoodam 함수와 dadas 함수를 구현하여 제출해야 한다. main 함수는 구현하면 안 된다. 채점기가 두 함수를 서로 다른 프로세스에서 각각 한 번 호출한다.

다음 두 함수를 구현해야 한다.

std::string yoodam(
    int N,
    std::vector<int> U,
    std::vector<int> V,
    int a,
    int b
);

int dadas(
    int N,
    std::vector<int> X,
    std::vector<int> Y
);

유담이 역할의 프로세스에서 yoodam 함수가 먼저 호출된다.

$M=|U|=|V|$이다. 각 $i$ ($1\le i\le M$)에 대해 $i$번 간선은 $U[i-1]$과 $V[i-1]$을 잇는다. 매개변수 $a$와 $b$는 추가할 간선의 두 끝점인 정점 번호이다. 즉, $e^*=(a,b)$이며, $a$번 정점과 $b$번 정점을 잇는 간선은 $G$에 존재하지 않는다.

그 후 다다스 역할의 새로운 프로세스에서 dadas 함수가 호출된다.

$M'=|X|=|Y|=M+1$이다. 각 $i$ ($1\le i\le M'$)에 대해 현재 $i$번 간선은 $X[i-1]$에서 $Y[i-1]$로 향한다. 정점 번호와 간선 번호는 yoodam 함수 호출 이후 각각 임의로 다시 매겨진다.

yoodam 함수는 길이가 $M+1$인 이진 문자열 $S$를 반환해야 한다.

$1\le i\le M$일 때, $S[i-1]=`0`$이면 $i$번 간선을 $U[i-1]$에서 $V[i-1]$로 향하게 하고, $S[i-1]=`1`$이면 $V[i-1]$에서 $U[i-1]$로 향하게 한다.

$S[M]=`0`$이면 추가 간선을 $a$에서 $b$로 향하게 하고, $S[M]=`1`$이면 $b$에서 $a$로 향하게 한다.

dadas 함수는 유담이가 추가한 간선의 현재 번호를 반환해야 한다. 반환값은 $1$ 이상 $M'$ 이하의 정수여야 한다.

• 하나의 채점 데이터마다 yoodam 함수와 dadas 함수가 서로 다른 프로세스에서 각각 한 번 호출된다.
• $3\le N\le 200\,000$.
• $N-1\le M\le \min\left(\cfrac{N(N-1)}2-1,399\,999\right)$.
• $1\le U[i]<V[i]\le N$ ($0\le i<M$).
• $G$는 단순 연결 무향 그래프이다.
• $1\le a<b\le N$.
• 간선 $(a,b)$는 $G$에 존재하지 않는다.
• $M'=M+1\le400\,000$.
• $1\le X[i],Y[i]\le N$ ($0\le i<M'$).

첨부된 sample_grader.cpp는 제출 코드의 yoodam 함수를 호출하고, 반환된 방향을 적용한 뒤 정점 번호와 간선 순서를 고정된 방식으로 섞는다. 그 후 같은 실행 안에서 dadas 함수를 호출한다.

Sample grader의 입력 형식은 다음과 같다.

$N\ M$ $U[0]\ V[0]$ $U[1]\ V[1]$ $\vdots$ $U[M-1]\ V[M-1]$ $a\ b$

Sample grader는 다음을 출력한다.

$`result`\ `hidden\_position`\ `answer`$

• $`result`$: yoodam의 반환값이 올바른 형식이고 $`answer`=`hidden\_position`$이면 $1$, 그렇지 않으면 $0$이다.
• $`hidden\_position`$: 정점 번호와 간선 순서를 섞은 뒤 추가 간선이 위치한 실제 간선 번호이다. yoodam의 반환 형식이 잘못되었다면 $-1$이다.
• $`answer`$: dadas 함수가 반환한 값이다. yoodam의 반환 형식이 잘못되었다면 $-1$이다.

이 예시에서는 추가 간선의 현재 번호가 $3$이고, dadas도 $3$을 반환하므로 첫 번째 값으로 $1$이 출력된다.

실제 채점에서는 yoodam과 dadas가 서로 독립된 프로세스에서 실행되며, 정점 번호와 간선 번호를 섞는 방법도 Sample grader와 다를 수 있다. 따라서 두 함수 사이에 전역 변수, 정적 변수, 파일 등의 상태를 공유하는 풀이는 실제 채점에서 올바르게 동작하지 않는다.