题目描述

有 $n$ 名尚未就业的程序员，编号为 $1\sim n$。其中编号 $1,2,3$ 的三个人是“天才”。

程序员之间存在 $m$ 对朋友关系。朋友关系是无向的。

现在两家公司轮流招聘程序员，公司 1 先手。每次轮到一家公司时，它可以招聘一名尚未被任何公司招聘的程序员，并且必须满足：

• 该公司的第一名员工可以任意选择；
• 从第二名员工开始，新招聘的程序员必须至少有一位朋友已经在这家公司工作。

如果某家公司在自己的某一回合已经无法按照规则招聘任何人，那么它从此停止招聘，而另一家公司仍可继续招聘。

两家公司都希望最终招聘到尽可能多的天才，并且双方都采用最优策略。每家公司都可以把第一名员工直接选为一名天才，因此至少能够保证得到一名天才。题目保证在最优博弈结果下，恰好有一家公司会得到三名天才中的两名。

请判断最终得到两名天才的是公司 1 还是公司 2。

双方在整个过程中都拥有完全信息。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示程序员 $a_i$ 与 $b_i$ 是朋友。

保证 $a_i\ne b_i$，同一对朋友关系不会重复出现（包括反向重复）。

输出格式

输出一个整数 1 或 2，表示在双方均采用最优策略时，最终招聘到两名天才的公司编号。

数据范围

$3\le n\le10^5$，$2\le m\le2\times10^5$。

样例 1

样例输入

4 3
1 4
2 4
3 4

样例输出

1

样例 2

样例输入

6 6
1 4
1 5
2 5
2 6
3 6
3 4

样例输出

2