## IPSC 2004

## Problem E – Electrical Circuits

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?

### Task specification

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.

### Input file specification

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).

### Output file specification

For each test case output a line with number P – the number of different
solutions for the test case.

### Example

**Input file**
1
4 4
1 1
1 3
3 3
3 1
1 2
2 3
3 4
4 1

**Output file**
2