Graph incidence nullspace
Work modulo \(p=1\,000\,000\,007\). A directed graph has (n) vertices and
(m) edges. Edge (j) goes from (u_j) to (v_j). Its incidence matrix (B)
has (B_{u_j,j}=-1), (B_{v_j,j}=1), and zero elsewhere.
Output a basis of the left nullspace
\[
\ker(B^T)=\{x\in\mathbb F_p^n:B^Tx=0\}.
\]
This space has one basis vector for each connected component.
Input
The first line contains (n,m). Each of the next (m) lines contains an edge
\(u_j,v_j\), using zero-based vertex indices.
Output
Print (k), followed by (k) vectors of length (n). They must form a basis of
\(\ker(B^T)\). Thus (k) equals the number of connected components.
Constraints
- \(1\le n\le 200\)
- \(0\le m\le 400\)
- \(0\le u_j,v_j<n\); self-loops are allowed