Given a bipartite graph having N vertices in each part and M edges, find the number of perfect matchings in it modulo 4.
Input format:
First line consists of a single integer T denoting the number of test cases.
First line of each case consists of two space separated integers denoting N and M.
Each of the following M lines consists of two space separated integers u and v, denoting that there is an edge between
vertex numbered u on the left side and vertex numbered v on the right side. Vertices on each side are enumerated independently starting from 0.
Output format:
For each test case, print a single number in a new line - number of perfect matchings modulo 4
Constraints:
\(1 \le T \le 10\)
\(1 \le N \le 50\)
\(0 \le M \le N * N\)
\(0 \le u, v \le N-1\)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
No editorial available for this problem.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor