Ian has an "Electric Circuits Soldering" exam today. At the begining of the test, each student is given an unfinished printed circuit board with some unconnected contacts. The task is to recognize the board and to finish connecting corresponding contacts. At the end, every contact should be connected to exactly one other contact. As Ian was too lazy to prepare for the exam, he must now guess which pairs of contacts to connect. Fortunately, he recognizes that some pairs of the contacts are incompatible and cannot be connected to each other. What is the probability that Ian will guess the correct answer?
Given the number of unconnected circuit contacts, their positions on the printed circuit board, and a list of pairs of contacts that can be connected to each other, count the number of all possible solutions of the test.
The input file describes several circuit boards; the number of the boards is given on the first line. Description of each board begins with two integers N and M - the number of unconnected contacts and the number of possible contact pairs. The contacts are numbered 1,2,...,N. The following N lines describe position of each contact by (x,y) coordinates on the board. Finally, the following M lines list the pairs of contacts that can be connected to each other (one pair per line).
For each test case output a line with number P – the number of different solutions for the test case.
1 4 4 1 1 1 3 3 3 3 1 1 2 2 3 3 4 4 1Output file
2