Edge Smuggling

※ Use C++17.

This is a two-step problem.

Yudam wants to secretly deliver one edge to Dadas.

The process acting as Yudam receives a simple connected undirected graph $G$ with $N$ vertices and an edge $e^*$ that does not belong to $G$. Yudam adds $e^*$ to $G$ and must assign a direction to every edge of the resulting graph.

The judge applies the directions returned by Yudam. It then independently renumbers all vertices and all edges in an arbitrary order. A fresh process acting as Dadas receives only the resulting simple connected directed graph. Dadas does not know any original vertex or edge number.

Dadas must return the current number of the edge added by Yudam.

No memory, file, global variable, or other state is shared between the two processes. The only information Yudam may pass to Dadas is the oriented graph itself. The strategy must succeed for every renumbering of the vertices and edges.

Include the provided header using #include "edgesmuggling.h" and implement the functions yoodam and dadas. Do not implement main. The judge calls the two functions once each in separate processes.

You must implement the following two functions.

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
);

The function yoodam is called first in the process acting as Yudam.

Let $M=|U|=|V|$. For each $i$ ($1\le i\le M$), edge $i$ connects $U[i-1]$ and $V[i-1]$. The parameters $a$ and $b$ are the vertex numbers of the two endpoints of the edge to be added. In other words, $e^*=(a,b)$, and the edge connecting vertices $a$ and $b$ does not belong to $G$.

The function dadas is then called in a fresh process acting as Dadas.

Let $M'=|X|=|Y|=M+1$. For each $i$ ($1\le i\le M'$), current edge $i$ is directed from $X[i-1]$ to $Y[i-1]$. The vertex numbers and edge numbers are independently renumbered in arbitrary orders after the call to yoodam.

The function yoodam must return a binary string $S$ of length $M+1$.

For $1\le i\le M$, if $S[i-1]=`0`$, orient edge $i$ from $U[i-1]$ to $V[i-1]$; if $S[i-1]=`1`$, orient it from $V[i-1]$ to $U[i-1]$.

If $S[M]=`0`$, orient the added edge from $a$ to $b$; if $S[M]=`1`$, orient it from $b$ to $a$.

The function dadas must return the current number of the edge added by Yudam. The return value must be an integer from $1$ to $M'$.

• For each judge case, yoodam and dadas are each called once in separate processes.
• $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$ is a simple connected undirected graph.
• $1\le a<b\le N$.
• Edge $(a,b)$ does not belong to $G$.
• $M'=M+1\le400\,000$.
• $1\le X[i],Y[i]\le N$ ($0\le i<M'$).

The attached sample_grader.cpp calls the submitted yoodam function, applies the returned directions, and renumbers the vertices and edges using a fixed deterministic shuffle. It then calls dadas in the same execution.

The input format of the sample grader is as follows.

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

The sample grader prints the following values.

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

• $`result`$: $1$ if the value returned by yoodam has a valid format and $`answer`=`hidden\_position`$; otherwise, $0$.
• $`hidden\_position`$: the actual current edge number of the added edge after the vertex and edge renumbering. It is $-1$ if the value returned by yoodam has an invalid format.
• $`answer`$: the value returned by dadas. It is $-1$ if the value returned by yoodam has an invalid format.

In this example, the current number of the added edge is $3$, and dadas also returns $3$, so the first printed value is $1$.

In the actual judge, yoodam and dadas run in separate processes, and the vertex and edge renumbering may differ from the sample grader. Therefore, a solution that shares state between the two functions through global variables, static variables, files, or similar mechanisms will not work in the actual judge.