Counting Bipartite Graphs

5

3 votes
Combinatorics, Easy, Graphs, Inclusion-Exclusion, Math
Problem

You are given two sets of vertices such that the first set contains n vertices labeled 1 to n and the second set contains m vertices labeled 1 to m.

Add edges between these vertices such that no two vertices from the same set are adjacent and each vertex is incident on at least one edge. Find out the number of graphs that can be formed under the above constraints.

CONSTRAINTS:
1nm106

INPUT:
A single line containing two integers n and m.

OUTPUT:
A single integer denoting the answer. Since the answer can be large, output it modulo 998244353 .

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Denote a pair (u,v) as an edge where u is a vertex from the first set and v from the second.

Then the edge sets for the 7 graphs are:

  1. (1,1),(2,2)
  2. (1,2),(2,1)
  3. (1,1),(1,2),(2,2)
  4. (1,1),(1,2),(2,1)
  5. (1,1),(2,1),(2,2)
  6. (1,2),(2,1),(2,2)
  7. (1,1),(1,2),(2,1),(2,2)
Editor Image

?