171 lines
No EOL
5 KiB
Python
171 lines
No EOL
5 KiB
Python
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)) |