Longest Trip

There are $N$ landmarks at Ópusztaszer, numbered from $0$ to $N-1$. Some pairs of landmarks are connected by roads, which run in both directions. Each pair of landmarks is connected by at most one road. The organizers do not know which landmarks are connected.

The density of the road network is at least $\delta$ if every three distinct landmarks have at least $\delta$ roads among them. In other words, for each triplet $(u, v, w)$ with $0 \le u < v < w < N$, at least $\delta$ of the pairs $(u,v)$, $(v,w)$ and $(u,w)$ are connected by a road.

The organizers know a positive integer $D$ such that the density of the road network is at least $D$. The value of $D$ cannot be greater than $3$.

The organizers can call the phone dispatcher to learn about road connections between certain landmarks. Each call takes two nonempty arrays of landmarks, $A[0], \ldots, A[P-1]$ and $B[0], \ldots, B[R-1]$. The landmarks in $A$ must be pairwise distinct, the landmarks in $B$ must be pairwise distinct, and no landmark may appear in both arrays.

For each call, the dispatcher checks every pair $i$, $j$ with $0 \le i < P$ and $0 \le j < R$. If any pair $A[i]$ and $B[j]$ is connected by a road, the dispatcher returns true. Otherwise it returns false.

A trip of length $l$ is a sequence of distinct landmarks $t[0], t[1], \ldots, t[l-1]$ where $t[i]$ and $t[i+1]$ are connected by a road for each $0 \le i \le l-2$. A trip of length $l$ is a longest trip if no trip of length $l+1$ or more exists.

Your task is to find a longest trip at Ópusztaszer by making calls to the dispatcher.

Constraints

• $3 \le N \le 256$
• The sum of $N$ over all calls to longest_trip does not exceed $1\,024$ in each test case.
• $1 \le D \le 3$