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

【题目描述】

兰姐姐是来自火星的女王。相信你们一定对兰姐姐不熟悉，她统领整个火星，在各方面拥有最高权力。很久很久以前，兰爸爸是火星的国王，去世以后，两个女儿争夺王位。火星上最聪明的人是辣椒酱，他帮助兰姐姐夺得了王位，而兰姐姐的姐姐Horse没有得到王位，便离开火星前往地球修行。

几年后，兰姐姐越来越思念姐姐，便决定到地球上找姐姐。 今天，她找到了自己失散已久的姐姐Horse的家，但是要进门就必须答对一个大难题，作为一个大犇犇犇，她很快就解出来了，你行吗？

题目是这样的： 现在有一个序列a，a的长度为n，一开始a[i]=i(1≤i≤n)，现在有m个操作，每个操作的格式是这样的：x y表示把当前的a[x]与a[y]交换。我们把这m个操作叫做一轮操作，现在问，在经过多少轮操作之后，序列a又会回到原来的样子（原来的样子就是指a[i]=i(1≤i≤n)）

【输入格式】

第一行，两个整数n，m，n表示a的长度，m表示操作数

接下来m行，每行一个操作x y，表示把当前的ax与ay交换保证（1≤x,y≤n）

【输出格式】

只有一个数，表示在经过多少轮之后，序列a又会回到原来的样子

【样例输入1】

4 4
1 4
3 4
2 3
1 4

【样例输出1】

3 ##【样例输入2】

5 3
1 2
2 3
4 5

【样例输出2】

6

【数据范围】

50％数据保证1≤n,m≤1000，答案小于等于1000

100％数据保证1≤n,m≤50000，答案小于等于10^18