Another task about trees

Consider a graph with $N$ vertices, initially devoid of edges. You are tasked with handling $M$ queries, which are of two types:

• Add an edge from vertex $v_1$ to vertex $v_2$, ensuring that $v_1$ and $v_2$ belong to different trees, and that $v_2$ is the root of its tree.

• Check if two vertices $a$ and $b$ are part of the same tree.

Solution

We will use the Union-Find data structure with path compression to efficiently manage these operations:

int n, m, l[NMAX];
int calc_leader (int v)
{
    if (l[v] != v)
        l[v] = calc_leader(l[v]);
    return l[v];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        l[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &z, &x, &y);
        if (z == 1)
            l[y] = x;
        else
            if (calc_leader(x) == calc_leader(y))
                printf("YES\n");
            else
                printf("NO\n");
    }
}

Your task is to design a test case that causes this solution to execute for an extended period. Specifically, the number of calls to the function calc_leader should be at least $1/4M{\log }_{2}M$.

Input

The input consists of two integers $N$ and $M$ ($1\le N\le 10^6$, $1\le M\le 10^5$, $M\le N$).

Output

Produce $M$ lines of output. The $i$-th line should be formatted as $1xy$ if the $i$-th query is to add an edge from vertex $x$ to vertex $y$, or $0xy$ if it is to check whether vertices $x$ and $y$ are in the same tree.

Examples