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$ (), edge connects and . The parameters and are the vertex numbers of the two endpoints of the edge to be added. In other words, , and the edge connecting vertices and does not belong to .

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

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

• 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)$.

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]$