Over the years, FJ has made a huge number of farmer friends all around the world. Since he hasn't visited 'Farmer Ted' from England and 'Boer Harms' from Holland for a while, he'd like to visit them. He knows the longitude of the farm where each of his worldwide friends resides. This longitude is an angle (an integer in the range 0..359) describing the farm's location on the Earth, which we will consider to be a circle instead of the more complex and traditional spherical representation. Except for the obvious discontinuity, longitudes increase when traveling clockwise on this circle. FJ plans to travel by airplane to visit his N (1 <= N <= 5,000) friends (whose farms are uniquely numbered 1..N). He knows the schedules for M (1 <= M <= 25,000) bidirectional flights connecting the different farms. Airplanes always travel shortest paths on the Earth's surface (i.e., on the shortest arc of a circle). There will always be a unique shortest path between two farms that are directly connected. No pair of antipodal farms (exactly opposite each other on the circle) is ever directly connected. Each airplane flight can be described as traveling in clockwise or counterclockwise direction around the Earth's surface. For example, a flight from longitude 30 to longitude 35 would be clockwise, as would be a flight from longitude 350 to longitude 10. However, a flight from longitude 350 to longitude 200 follows a shortest path counterclockwise around the circle. FJ would find it very cool if he could make a trip around the world, visiting some of his friends along the way. He'd like to know if this is possible and if so, what is the minimum number of flights he can take to do so. He wants to start and finish his journey at the location of his best friend (the one listed first in the input below). In order to make sure he actually circles the Earth, he wants to ensure that the clockwise distance he travels is different from the counterclockwise distance he travels.

这些年，农夫约翰在国际上交了一大批开农场的朋友．由于他有一段时间没有去见过英国的农夫泰德和荷兰的农夫波尔，所以他想去访问他们, 他知道每个朋友的农场的经度．经度（从0到359）是一种角度描述农场在地球上位置的方法，我们把地球看成一个圆，正如我们所熟知的，经度在地球上沿着顺时针方向增长, 农夫约翰打算乘飞机去访问他的N(1≤N≤5000)个朋友（用1到N来表示）．他知道在这些农场之间有M(1≤M≤25000)条双向的航线，当然飞机总是沿着地面上最短的路径飞行的（就是圆上的最短弧长）．两个农场之间的航线一定是最短的，也就是说如果育两个农场在直径两端，那么他们之间一定不存在航线．所以任何一次航行都可以被描述成顺时针或是逆时针的．比如说，经度30到经度35是顺时针的，经度350到经度10也是顺时针的，而经度350到经度200是逆时针的．

农夫约翰为了耍酷，决定要经过几个朋友的农场做到环球旅行，他想知道这是否可能，如果可能最少要乘几次飞机． 他想在他最好的朋友（也就是列表中的第一个）的农场上开始和完成这次旅行．为了保证这是一次环球航行，回到终点时，顺时针经过的路程不能等于逆时针经过的路程．