Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Matrix Multiplication
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 1672Accepted: 519

Description

Many studies have been done on developing efficient algorithms to calculate matrix multiplication. But it remains as a hard topic today. In this problem you are to calculate the 2006th power of a square Boolean matrix where addition and multiplication are defined as follows:

ABA + B
000
011
101
111

Truth Table of Addition

ABAB
000
010
100
111

Truth Table of Multiplication

Let A be a square matrix. The zeroth power of A is the identity matrix. The n-th (n > 0) power of A is the product of A and its (n 1)-th power.

Input

The input contains multiple test cases. Each test cases consists of some lines:

  • Line 1: Contains two integers K (K < 1000) and M (0 M ≤ 10K), indicating the dimension of the matrix is K × K and K + M elements of the matrix are 1’s.
  • Lines 2 ~ M + 1: Each contains two integers i and j (0 ≤ i, j < K, ij), indicating the element in the (i + 1)-th row and (j + 1)-th column is 1.

All elements on the primary diagonal of the matrix are 1’s.

Output

For each test case output one line containing the number of elements that are 1s in the 2006th power of the given matrix.

Sample Input

3 4
1 2
2 1
0 1
0 2

Sample Output

7

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator