Archaeologist's Trouble

Time Limit: 1 Second    Memory Limit: 32768 KB

Lazy Genius recently received a detailed map of a tomb. He believed that there should be some rare relics in the tomb.

As known to all, there are many lethal traps in the tomb, certainly, including the entrance door. If you break into the tomb, you might be killed. Well, don't worry since you have a computer to help you. The door has N locks. Beside the door, there are M switches. Each switch controls several locks. When you press one switch, the corresponding locks will change their status (locked->unlocked, unlocked->locked). If any lock changes its status more than three times, all the locks will lock up and can't be unlocked forever.

Lazy wants to open the door as soon as possible. Because of your excellent accomplishment in the previous missions, Lazy turned to you, believing that you could help him.

Input

The input contains several test cases, separately by a blank line in-between.

The first line of each case contains two integers, N (0 < N < 30) and M (0 < M < 60). Then M lines follow. Each line begins with an integer k, and then followed by k integers that indicate the locks controlled by one switch.

Output

For each test case, output in one line the least number of switchs that should be pressed to open the door. If such a number does not exist, print "~~~~><~~~~".

Sample Input

4 3
3 1 2 3
2 3 4
1 4

Sample Output

2

Submit

Source: ZOJ Monthly, November 2003