This is an approximate problem.
Given a connected undirected graph G with N vertices and M edges. A path P of length K is a sequence of K vertices such that every two consecutive vertices are connected by an edge. You want to choose a path P from graph G such that LIS(P)⋅LDS(P) is maximized. LIS(P) is the longest increasing subsequence of P and LDS(P) is the longest decreasing subsequence of P .
Input
The first line contains three integers - N,M,T where T(1≤T≤15) is the type of the test.
The next M lines contain two integers - U,V(1≤U≠V≤N) meaning there is an edge between U and V .
Output
The first line contains the length of the path - K(1≤K≤N) .
The second line contains the path P−P1,P2,…,PK (1≤Pi≤N,i≠j⟹Pi≠Pj) . For every i (1≤i<K) there must be edge (Pi,Pi+1) in the graph G .
Scoring
Your score will be equal to 100⋅LIS(P)⋅LDS(P)M . You need to maximize this score.
Test Generation
The tests are generated by three different methods.
In the first method, from all N(N−1)2 possible edges, M are chosen with the same probability. This process is repeated while the chosen graph isn't connected. Below is attached an approximate pseudocode:
for i in range(1,N)
for j in range(1,i - 1)
E.append(i,j)
while (true)
random_shuffle(E)
edges = E[1..M]
if edges is connected
break
for (i,j) in edges
add_edge(i,j)
In the second method, a forest of paths with length chosen uniformly in the interval [1,W] is created. Then, random edges are added to connect the paths in the forest. Below is an approximate pseudocode:
V = empty array
while (sum(V) <= N)
V.append(min(N - sum(V),rand(1,W)))
sz = 0
for i in V
if sz != 0
add_edge(rand(sz + 1,sz + i),rand(1,sz))
++sz
for j in range(1,i - 1)
add_edge(sz,sz + 1)
++sz
while (number_of_edges < M)
a = rand(1,n)
b = rand(1,n)
if a != b and (a,b) is not an edge
add_edge(a,b)
randomly permute vertices
Below is an approximate pseudocode for the third method:
for i in range(2,N + 1)
j = rand(max(1,i - 16),i - 1)
if i == N + 1
add_edge(1,j)
else
add_edge(i,j)
p = 32
while (p <= N)
for i in range(1,N)
while (true)
j = rand(i + 1,i + p)
if j > N
j -= N
if (i,j) is not an edge
add_edge(i,j)
break
p = p * 2
randomly permute vertices
Note that the tests are ordered in the same way as presented in the table above.
Test data will be regenerated with different seeds after the contest.
We have that P=(2,3,4,1), LIS(P)=3 (2,3,4) and LDS(P)=2 (4,1). The score will be equal to 6004=150 . Note that if we would chose P=(2,3,4,5) , we would obtain score 100 instead.