Travel Company's Strategy

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

Problem Description

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:

  1. Each of the N cities belongs to exactly one tour.
  2. 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.
 

Input

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.

Output

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

Sample Input

2 1
1 2

2 2
1 2
2 1

Sample Output

0
1

Source

dut200901102

Manager

Information
Solved Number4
Submit Number7
Problem Tags
matrices
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel