Very Sparse Table

시간 제한30초메모리 제한2048 MB

문제

This is an interactive problem.

You are given a directed graph $G$ on vertices numbered $0$ to $n$. Initially, $G$ contains exactly $n$ edges of the form $v \to v + 1$. Your task is to add some edges to this graph in such a way that for every two vertices $v, u$ ($v < u$) there exists a directed path from $v$ to $u$ consisting of at most three edges. There are also two additional requirements you must meet:

  1. You can add an edge $a \to c$ if and only if there exists such $b$ that edges $a \to b$ and $b \to c$ are already present in $G$.
  2. You can add at most $6 \cdot n$ edges in total.