간선 소매넣기

※ 현재 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$ ()에 대해 번 간선은 과 을 잇는다. 매개변수 와 는 추가할 간선의 두 끝점인 정점 번호이다. 즉, 이며, 번 정점과 번 정점을 잇는 간선은 에 존재하지 않는다.

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

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

• 하나의 채점 데이터마다 yoodam 함수와 dadas 함수가 서로 다른 프로세스에서 각각 한 번 호출된다.
• $3\le N\le 200\,000$.
• $N-1\le M\le \min\left(\cfrac{N(N-1)}2-1,399\,999\right)$.

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

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

$N\ M$ $U[0]\ V[0]$ $U[1]\ V[1]$