Kotlin Heroes 比赛即将结束。这次有$$$n$$$程序员参加了比赛。现在组织者也在考虑如何娱乐观众。其中一种可能性是举办抽奖活动。所以现在他们决定在观众中进行一项调查。
组织者总共向 $$$m$$$ 观众提出了两个问题:
1. 谁会获得第一名?
2. 谁会获得最后一名?
收到答案后,主办方根据猜对的程序员数量对所有观众进行了排名。假设有 $$$c_2$$$ 观众猜对了第一名和最后一名,$$$c_1$$$ 观众猜对了第一名或最后一名,还有 $$$c_0$$$ 观众根本没有猜对。所有 $$$c_2$$$ 观看者将获得 $$$1$$$ 排名,所有具有一个正确答案的观看者将获得 $$$c_2 + 1$$$ 排名,所有剩余观看者将获得 $$$c_2 + c_1 + 1$$$ 排名。
您是接受采访的观众之一。此外,作为组织者之一,您可以访问调查结果,但不能访问竞赛结果。算算,按照主办方的排名系统,你最差的排名是多少?
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 1000$$$; $$$1 \le m \le 2 \cdot 10^5$$$)——参与比赛的程序员数量和接受调查的观众数量。
接下来的 $$$m$$$ 行包含观众的答案。第 $$$i$$$ 行包含两个整数 $$$f_i$$$ 和 $$$l_i$$$ ($$$1 \le f_i, l_i \le n$$$; $$$f_i \ne l_i$$$) - 在第 $$$i$$$ 观众看来将获得第一和最后位置的程序员的索引。
为简单起见,您是观众中的第一个,因此您的答案是 $$$f_1$$$ 和 $$$l_1$$$。
输出
打印单个整数——根据组织者的排名系统,您可能获得的观众中最差的排名(排名越高——当然越差)。
示例
输入 #1
2 3 1 2 2 1 2 1
输出 #1
3
输入 #2
3 6 3 1 3 2 2 1 3 2 3 2 3 1
输出 #2
4
注意
在第一个示例中,如果第二个程序员获得第一名,而第一个程序员获得最后一名,那么您将得到 $$$0$$$ 正确答案,而其他两个观众 - $$$2$$$ 正确答案。这就是为什么你的排名(在最坏的情况下)将是 $$$c_2 + c_1 + 1$$$ $$$=$$$ $$$2 + 0 + 1 = 3$$$。
在第二个示例中,例如,如果第三个程序员获得第一名,第二个程序员获得最后一名,那么您将得到 $$$1$$$ 正确答案。观众 $$$2$$$、$$$4$$$ 和 $$$5$$$ 将有 $$$2$$$ 正确答案,观众 $$$6$$$ — $$$1$$$ 正确答案,观众 $$$3$$$ — $$$0$$$ 正确答案。因此,您的排名将等于 $$$c_2 + 1$$$ $$$=$$$ $$$3 + 1 = 4$$$。 (请注意,观众 $$$6$$$ 将具有相同的排名 $$$4$$$)。