Graph Isomorphism and Non-Isomorphic Graph Count

This problem consists of two parts. In the first part, you are given two simple undirected graphs A and B. Two graphs A and B are considered isomorphic if there exists a relabeling (i.e. a permutation \( \pi \)) of the vertices of A such that the vertex set and the edge set of A correspond exactly to those of B. In other words, for any pair of vertices \( i \) and \( j \), an edge exists between them in graph A if and only if an edge exists between \( \pi(i) \) and \( \pi(j) \) in graph B.

In the second part, you are given an integer \( N \), representing the number of vertices. A simple graph on \( N \) vertices can have at most \( \frac{N(N-1)}{2} \) edges and in total there are \( 2^{\frac{N(N-1)}{2}} \) possible graphs. However, many of these graphs are isomorphic to one another. Your task is to compute the number of non-isomorphic graphs on \( N \) vertices (i.e. count each isomorphism class exactly once).

Input Format: The first integer in the input indicates which part of the problem to solve. If the first integer is 1, you will be given two graphs to test for isomorphism. If it is 2, you will be given a single integer \( N \) for which you must compute the number of non-isomorphic graphs modulo \( 10^9+7 \). The details are described below.

Graph Isomorphism Query (Query Type 1):

• The first integer is 1.
• The next integer is \( n \) (the number of vertices; vertices are numbered from 1 to \( n \)).
• The following integer is \( m_1 \), the number of edges in graph A.
• The next \( m_1 \) lines each contain two integers \( u \) and \( v \) representing an undirected edge in graph A.
• Then an integer \( m_2 \) follows, the number of edges in graph B.
• The next \( m_2 \) lines each contain two integers \( u \) and \( v \) representing an undirected edge in graph B.

Non-Isomorphic Graph Count Query (Query Type 2):

• The first integer is 2.
• The next integer is \( N \) (the number of vertices).
• You must output the number of non-isomorphic graphs on \( N \) vertices modulo \( 10^9+7 \). Note: For the purpose of this problem, \( N \) will be small (for example, \( N \leq 6 \)), so you may use precomputed values:
  \( N=1: 1 \), \( N=2: 2 \), \( N=3: 4 \), \( N=4: 11 \), \( N=5: 34 \), \( N=6: 156 \).

inputFormat

The input starts with a single integer indicating the query type. If it is 1, then the input format is:

1
n
m1
u1 v1
u2 v2
... (m1 edges for graph A)
m2
u1 v1
u2 v2
... (m2 edges for graph B)

If the query type is 2, then the input format is:

2
N

outputFormat

For query type 1, output a single line containing either YES if the two graphs are isomorphic, or NO otherwise.

For query type 2, output a single integer denoting the number of non-isomorphic graphs on \( N \) vertices modulo \( 10^9+7 \).

sample

1
3
3
1 2
2 3
1 3
3
1 3
2 3
1 2

YES