题目描述

题目译自 Open Olympiad in Informatics 2016 Day2 T1 「Чемпионат Юпитера / Jupiter’s Championship」。

众所周知，六月将在弗拉特兰举办木星足球锦标赛。共有 $n$ 支球队将参加比赛，比赛采用单循环赛制，每支球队将与其他每支球队进行一场比赛。

在木星，足球队服有 $m$ 种颜色。每支球队会携带两套不同颜色的队服。显然，在比赛中，一支球队的所有球员必须穿着同一颜色的队服，且与对手球队的队服颜色不同。

为了裁判本次锦标赛的所有比赛，幻想外星足球协会的主席约瑟夫受邀担任裁判。在每场比赛开始前，约瑟夫会为每支球队指定一个队服颜色，供球员上场时穿着。当然，他只能从每支球队携带的两种颜色中选择。之后，约瑟夫会为自己选择一个与两支球队队服颜色都不同的颜色穿上。这样，两支球队和裁判在场上将穿着不同颜色的队服。球队和约瑟夫的任何队服都可以在锦标赛的任意数量比赛中使用。

约瑟夫在锦标赛前采购裁判服，依据的是各球队携带的队服颜色信息。由于约瑟夫希望为协会节省资金，他想购买尽可能少的裁判服，但要确保足够覆盖所有比赛。这对于一个普通的足球裁判来说任务过于复杂，因此他向你寻求帮助。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(2 \leq n \leq 100000, 2 \leq m \leq 10^{9})$，分别表示参加锦标赛的球队数量和队服颜色的可能种类数量。

接下来的 $n$ 行，每行包含两个不同的整数（范围从 $1$ 到 $m$），表示编号为 $i$ 的球队携带的两种队服颜色。

输出格式

第一行输出一个整数，表示约瑟夫需要购买的最小裁判服数量，以覆盖所有球队对之间的比赛。如果无解，则输出一行包含 -1。

第二行输出这些裁判服的颜色。

如果存在多个最优解，可以输出其中任意一个。

3 4
1 2
2 3
1 4

1
1

在第一个样例中，约瑟夫只需购买一件颜色为 $1$ 的裁判服，因为在任何可能的比赛中，球队都可以从其携带的队服颜色中选择，而不选择颜色 $1$。例如，在第一支和第二支球队的比赛中，可以指定第一支球队穿颜色 $2$，第二支球队穿颜色 $3$。

5 3
1 2
2 3
2 3
3 1
1 2

2
3 1

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。