Longest Trip

The IOI 2023 committee is in trouble – they completely forgot to plan the upcoming Ópusztaszer trip! In Ópusztaszer there are (N) landmarks numbered from (0) to (N-1) and some pairs of landmarks are connected by bidirectional roads. There is at most one road between any pair, but the committee does not know which pairs are connected.

The road network is said to have a density of at least (\delta) if for every three distinct landmarks ((u, v, w)) with (0 \le u < v < w < N), at least (\delta) of the three possible pairs ((u,v)), ((v,w)) and ((u,w)) are connected by a road. The committee already knows that there is some positive integer (D) (with (D \le 3)) such that the density is at least (D).

The committee can ask the telephone operator whether there is a road between two groups of landmarks. In each query, you provide two nonempty arrays of landmarks (A = [A[0], \ldots, A[P-1]]) and (B = [B[0], \ldots, B[R-1]]) which are pairwise disjoint. The operator will check every pair (A[i]) and (B[j]) (for all valid (i) and (j)) and report (true) if at least one such pair is connected by a road, otherwise (false).

A route of length (l) is defined as a sequence of (l) distinct landmarks (t[0], t[1], \ldots, t[l-1]) such that for every (0 \le i \le l-2) there is a road connecting (t[i]) and (t[i+1]). A longest trip is defined as a route that has maximum possible length (i.e. there is no route of length at least (l+1) if this route has length (l)).

Your task is to help the committee find one longest trip by making queries via the function call

int[] longest_trip(int N, int D)

which can call the helper function

bool are_connected(int[] A, int[] B)

at most 32,640 times during a single call (with global limits over all calls). The values of (N) and (D) (and the underlying road network) remain fixed in all calls.

Note: All formulas are in (\LaTeX) format.

inputFormat

The input starts with a line containing three integers (N), (D) and (M), where (N) is the number of landmarks, (D) is the guaranteed density parameter, and (M) is the number of roads. Then (M) lines follow, each containing two integers (u) and (v) (with (0 \le u, v < N) and (u \neq v)) representing a road between landmarks (u) and (v). It is guaranteed that the road network has density at least (D).

outputFormat

Output a longest trip found in the network as a sequence of space-separated landmark indices. The solution must represent a valid route in the graph where consecutive landmarks are connected by a road. If there are multiple longest trips, any one is acceptable.

sample

4 3 6
0 1
0 2
0 3
1 2
1 3
2 3

0 1 2 3