Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

National Days is coming, and Travel Company is planning to make a new market strategy.

The country has *N* cities and connected by *M* one-way streets.

You are the director of a travel agency, and you want to create a travel plan contains some tours around the country which satisfy the following conditions:

- Each of the
*N*cities belongs to exactly one tour. - Each tour is a cycle which consists of at least 2 places and visits each place once (except for the place we start from which is visited twice).

Now you wonder how many plans are there he can choose for his company.

There are multiple test cases.

The first line of each test case contains two integers*N, M. (1 ≤ N ≤ 100, 0 ≤ M ≤ N * (N - 1))*

The next*M* lines contains two integer *a, b* indicating this road is from *a* to *b*. *(1 ≤ a, b ≤ N)*

There is no self-loop and multi-edges in the input.

The first line of each test case contains two integers

The next

There is no self-loop and multi-edges in the input.

For each test case, you should output the answer modulo *2*.

2 1 1 2 2 2 1 2 2 1

0 1

dut200901102