import sys

# Читаем весь ввод разом
data = sys.stdin.read().split()
if not data:
    sys.exit(0)

n = int(data[0])
m = int(data[1])

g = [[] for _ in range(n + 1)]
idx = 2
for _ in range(m):
    u = int(data[idx])
    v = int(data[idx + 1])
    g[u].append(v)
    g[v].append(u)
    idx += 2

# Структуры для DFS-дерева
tree_adj = [[] for _ in range(n + 1)]
sz = [1] * (n + 1)
parent = [0] * (n + 1)
visited = [False] * (n + 1)

# Строим DFS-дерево итеративно, чтобы не словить RecursionError
stack = [1]
visited[1] = True
order = []
edge_idx = [0] * (n + 1)

while stack:
    u = stack[-1]
    found = False
    while edge_idx[u] < len(g[u]):
        v = g[u][edge_idx[u]]
        edge_idx[u] += 1
        if not visited[v]:
            visited[v] = True
            parent[v] = u
            tree_adj[u].append(v)
            stack.append(v)
            found = True
            break
    if not found:
        order.append(u)
        stack.pop()

# Считаем размеры поддеревьев (снизу вверх)
for u in order:
    if parent[u] != 0:
        sz[parent[u]] += sz[u]

# Поиск единственного верного пути сверху вниз
u = 1
dp = 1
path = []
target_found = -1

while u != 0:
    path.append(u)
    rem = n - len(path)
    if rem == 0:
        break
        
    children = tree_adj[u]
    
    # Проверяем, можем ли мы остановиться прямо сейчас
    if rem % 2 == 0 and rem > 0:
        target = rem // 2
        temp_dp = dp
        mask = (1 << (target + 1)) - 1
        temp_dp &= mask
        
        # Мысленно добавляем всех детей текущей вершины в рюкзак
        for c in children:
            temp_dp = (temp_dp | (temp_dp << sz[c])) & mask
            
        if temp_dp & (1 << target):
            target_found = target
            break
            
    if not children:
        break
        
    # Если мы не можем остановиться, мы обязаны шагнуть в самое тяжелое поддерево,
    # чтобы "раздробить" его на части.
    heavy_child = max(children, key=lambda x: sz[x])
    
    # Все остальные дети навсегда "отваливаются" от пути, добавляем их в рюкзак
    mask_dp = (1 << ((n + 2) // 2)) - 1
    dp &= mask_dp
    for c in children:
        if c != heavy_child:
            dp = (dp | (dp << sz[c])) & mask_dp
            
    u = heavy_child

if target_found != -1:
    # Мы нашли путь! Теперь соберем все отвалившиеся поддеревья, из которых мы набрали target
    items = []
    for i in range(len(path) - 1):
        curr_node = path[i]
        next_node = path[i+1]
        for c in tree_adj[curr_node]:
            if c != next_node:
                items.append((c, sz[c]))
                
    last_node = path[-1]
    for c in tree_adj[last_node]:
        items.append((c, sz[c]))
        
    # Честный алгоритм рюкзака с восстановлением ответа (только для собранных компонент)
    track = [-1] * (target_found + 1)
    dp_track = 1
    
    for i, (c, w) in enumerate(items):
        nxt = (dp_track << w) & ((1 << (target_found + 1)) - 1)
        diff = nxt & ~dp_track
        if diff:
            # Быстрый битовый трюк для итерации только по новым битам
            bit = (diff & -diff)
            while diff > 0:
                pos = bit.bit_length() - 1
                if pos <= target_found and track[pos] == -1:
                    track[pos] = i
                diff ^= bit
                bit = (diff & -diff)
            dp_track |= nxt
        if dp_track & (1 << target_found):
            break
            
    used_items = set()
    curr_w = target_found
    while curr_w > 0:
        idx = track[curr_w]
        used_items.add(idx)
        curr_w -= items[idx][1]
        
    a_ans = []
    b_ans = []
    
    # Раскидываем полные поддеревья по комнатам А и Б
    for i, (c, w) in enumerate(items):
        comp_nodes = []
        q = [c]
        h = 0
        while h < len(q):
            curr_node = q[h]
            h += 1
            comp_nodes.append(curr_node)
            for child in tree_adj[curr_node]:
                q.append(child)
                
        if i in used_items:
            a_ans.extend(comp_nodes)
        else:
            b_ans.extend(comp_nodes)
            
    # Вывод
    print(len(path), len(a_ans))
    print(*path)
    print(*a_ans)
    print(*b_ans)
else:
    # Железобетонный фолбек (теоретически недостижим на валидных данных)
    half = (n - 1) // 2
    print(1, half)
    print(1)
    print(*range(2, 2 + half))
    print(*range(2 + half, n + 1))