该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

从前有一个和谐的OI班级，班里有 $n$ 个男生，有$0$个女生，男生编号为 $1, 2, \dots, n$。

老师要把他们分成若干两人小组，每个人最多属于一个小组。 已知一些条件：第 $v$ 个男生和第 $u$ 个男生愿意组成小组。

请求出班级里最多能组成多少个小组，并输出任意一组最优分组方案。

Format

Input

第一行输入两个正整数 $n, m$，保证 $n \ge 2$。

接下来 $m$ 行，每行两个整数 $v, u$，表示 $v$ 号和 $u$ 号男生愿意组成小组。 保证：$1 \le v,u \le n$，$v \neq u$，且相同条件不会重复出现。

Output

第一行输出一个整数，表示最多能组成的小组数量。

第二行输出 $n$ 个整数，表示一组最优方案： 第 $v$ 个整数代表 $v$ 号男生所在小组的搭档编号；若未组队，输出 $0$。

Samples

10 20
9 2
7 6
10 8
3 9
1 10
7 1
10 9
8 6
8 2
8 1
3 1
7 5
4 7
5 9
7 8
10 4
9 1
4 8
6 3
2 5

5
9 5 6 10 2 3 8 7 1 4

Limitation

$1≤n≤500,1≤m≤124750$.