This is a codeforces Div 1 contest question, just guvw me the python code so that i can copy paste and submit it. 
F. Dora's Paint
time limit per test3 seconds
memory limit per test512 megabytes
Sadly, Dora poured the paint when painting the class mural. Dora considers the mural as the matrix b of size n×n. Initially, bi,j=0 for all 1≤i,j≤n.

Dora has only two brushes which have two different colors. In one operation, she can paint the matrix with one of two brushes:

The first brush has color 1 on it and can paint one column of the matrix. That is, Dora chooses 1≤j≤n and makes bi,j:=1 for all 1≤i≤n;
The second brush has color 2 on it and can paint one row of the matrix. That is, Dora chooses 1≤i≤n and makes bi,j:=2 for all 1≤j≤n.
Dora paints the matrix so that the resulting matrix b contains only 1 and 2.

For a matrix b, let f(b) denote the minimum number of operations needed to turn the initial matrix (containing only 0) into b. The beauty of a matrix b is the number of ways to paint the initial matrix in exactly f(b) operations to turn it into b. If there's no way to turn the initial matrix into b, the beauty of b is 0.

However, Dora made a uniformly random mistake; there's exactly one element different in the matrix a given to you from the real matrix b. That is, there is exactly one pair (i,j) such that ai,j=3−bi,j.

Please help Dora compute the expected beauty of the real matrix b modulo 998244353 (all possible n2 mistakes have equal probability).

Since the size of the matrix is too large, Dora will only tell you the positions of m elements of color 1, and the remaining n2−m elements have color 2.

Input
Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n and m (2≤n≤2⋅105, 0≤m≤min(106,n2)) — the size of the matrix and the number of elements of color 1.

Then m lines follow, each containing two positive integers xi and yi (1≤xi,yi≤n) — denoting that axi,yi=1.

It is guaranteed that if i≠j, then (xi,yi)≠(xj,yj).

It is also guaranteed that the sum of n over all test cases does not exceed 4⋅105, and the sum of m over all test cases does not exceed 106.

Output
For each test case, output a single integer — the expected beauty of the real matrix b, modulo 998244353.

Example
inputCopy
7
2 2
1 1
1 2
2 1
1 1
3 2
1 1
3 3
6 0
5 10
1 1
1 2
1 3
2 1
2 3
5 1
5 2
5 3
5 4
5 5
3 5
1 1
1 3
2 2
3 1
3 3
4 3
1 1
2 3
2 4
outputCopy
1
499122178
665496236
120
79859554
776412275
1
Note
In the first test case, the matrix a=[1212]. Let's consider changing the element (1,1) to calculate the answer.

It can be proved that the minimum steps to paint the initial matrix into [2212] is 3. We can first paint the first row into color 2, then paint the second column into color 1, and finally paint the second row into color 2. The process is listed below:

[0000]⇒[2020]⇒[2011]⇒[2212]

It can be proved that this is the only way to paint the matrix in 3 steps. So the beauty of the matrix [2212] is 1. Similarly, if any other element of the matrix is changed, the beauty is always 1, so the expected beauty of the real matrix b is 1.

In the second test case, the matrix a=[1222]. Let's consider changing the element (2,2) to calculate the answer.

It can be proven that it's impossible to paint the initial matrix into [1221], so its beauty is 0. If any other element of the matrix is changed, the beauty is always 2, so the expected beauty is 0+2+2+24=64≡499122178(mod998244353