← 返回题目列表

Codeforces · 1220/D

D. 亚历克斯和朱利安

中文机器翻译题面 查看原题

Boy Dima 给了 Julian 一份生日礼物 — 设置由正整数组成的 $$$B$$$。然而,他不知道,朱利安讨厌集合,却更喜欢二分图!

Julian 几乎心烦意乱,但她的朋友 Alex 说,他可以使用这个集合以这样的方式构建一个无向图:让所有整数为顶点,然后将任意两个 $$$i$$$ 和 $$$j$$$ 用边连接起来,如果 $$$|i - j|$$$ 属于 $$$B$$$。

不幸的是,Julian 不喜欢这个使用 $$$B$$$ 构建的图表。 Alex 决定纠正这种情况,因此他想从 $$$B$$$ 中删除一些数字,以便使用新集合构建的图是二分图。这项任务的困难在于 Alex 必须使用的图具有无限数量的顶点和边!独自解决这个任务是不可能的,所以亚历克斯向你寻求帮助。编写一个程序,从 $$$B$$$ 中删除最小大小的子集,以便在新集合上构建的图是二分图。

回想一下,如果该图的所有顶点都可以分为两个不相交的集合,使得每条边都连接来自不同集合的顶点,则该图是二分图。

输入

第一行包含一个整数 $$$n ~ (1 \leqslant n \leqslant 200\,000)$$$ — $$$B$$$ 的大小

第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n ~ (1 \leqslant b_i \leqslant 10^{18})$$$ — $$$B$$$ 的数量,所有 $$$b_i$$$ 都是唯一的

输出

在第一行打印单个整数 $$$k$$$ – 删除元素的数量。在第二行中打印 $$$k$$$ 整数 - 已删除元素的值。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
1 2 3

输出 #1

1
2

输入 #2

2
2 6

输出 #2

0