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) \cdot 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 \le T \le 15)\) is the type of the test.

The next \(M\) lines contain two integers - \(U,V (1 \le U \neq V \le N)\) meaning there is an edge between \(U\) and \(V\) .

Output

The first line contains the length of the path - \(K\)\((1 \le K \le N)\) .

The second line contains the path \(P - P_1, P_2, \dots, P_K\) \((1 \le P_i \le N, i \neq j \implies P_i \neq P_j)\) . For every \(i \ (1 \le i < K)\) there must be edge \((P_i, P_{i + 1})\) in the graph \(G\) .

Scoring

Your score will be equal to \(\frac{100 \cdot LIS(P) \cdot 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 \(\frac{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.