Longest Trip

문제

The IOI 2023 organizers are in big trouble! They forgot to plan the trip to Ópusztaszer for the upcoming day. But maybe it is not yet too late ...

There are $NN$ landmarks at Ópusztaszer indexed from $00$ to $N-1N-1$. Some pairs of these landmarks are connected by bidirectional roads. Each pair of landmarks is connected by at most one road. The organizers don't know which landmarks are connected by roads.

We say that the density of the road network at Ópusztaszer is at least $\delta \backslash delta$ if every $33$ distinct landmarks have at least $\delta \backslash delta$ roads among them. In other words, for each triplet of landmarks $(u,v,w)(u,\; v,\; w)$ such that $0\le u<v<w<N0\; \backslash le\; u\; \backslash lt\; v\; \backslash lt\; w\; \backslash lt\; N$, among the pairs of landmarks $(u,v),(v,w)(u,v),\; (v,w)$ and $(u,w)(u,w)$ at least $\delta \backslash delta$ pairs are connected by a road.

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

The organizers can make calls to the phone dispatcher at Ópusztaszer to gather information about the road connections between certain landmarks. In each call, two nonempty arrays of landmarks $[A[0],\dots ,A[P-1]][A[0],\; \backslash ldots,\; A[P-1]]$ and $[B[0],\dots ,B[R-1]][B[0],\; \backslash ldots,\; B[R-1]]$ must be specified. The landmarks must be pairwise distinct, that is,

• $A[i]\mathrm{\ne }A[j]A[i]\; \backslash neq\; A[j]$ for each $ii$ and $jj$ such that $0\le i<j<P0\; \backslash le\; i\; \backslash lt\; j\; \backslash lt\; P$;
• $B[i]\mathrm{\ne }B[j]B[i]\; \backslash neq\; B[j]$ for each $ii$ and $jj$ such that $0\le i<j<R0\; \backslash le\; i\; \backslash lt\; j\; \backslash lt\; R$;
• $A[i]\mathrm{\ne }B[j]A[i]\; \backslash neq\; B[j]$ for each $ii$ and $jj$ such that $0\le i<P0\; \backslash le\; i\; \backslash lt\; P$ and $0\le j<R0\backslash le\; j\; \backslash lt\; R$.

For each call, the dispatcher reports whether there is a road connecting a landmark from $AA$ and a landmark from $BB$. More precisely, the dispatcher iterates over all pairs $ii$ and $jj$ such that $0\le i<P0\; \backslash le\; i\; \backslash lt\; P$ and $0\le j<R0\backslash le\; j\; \backslash lt\; R$. If, for any of them, the landmarks $A[i]A[i]$ and $B[j]B[j]$ are connected by a road, the dispatcher returns true. Otherwise, the dispatcher returns false.

A trip of length $ll$ is a sequence of distinct landmarks $t[0],t[1],\dots ,t[l-1]t[0],\; t[1],\; \backslash ldots,\; t[l-1]$, where for each $ii$ between $00$ and $l-2l-2$, inclusive, landmark $t[i]t[i]$ and landmark $t[i+1]t[i+1]$ are connected by a road. A trip of length $ll$ is called a longest trip if there does not exist any trip of length at least $l+1l+1$.

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