Given two bidirectional graphs ~S~ and ~T~, can you determine if they are isomorphic?

Input Specification

The first line will contain two integers, ~N, M~ ~(1 \le N \le 8, 1 \le M \le N^2)~, the number of nodes and edges in graph ~S~ and graph ~T~, respectively.

The next ~M~ lines will each contain two integers, ~a_i, b_i~ ~(1 \le a_i, b_i \le N)~, denoting nodes ~a_i~ and ~b_i~ are connected by an edge in graph ~S~. There may be self-loops and duplicate edges between two nodes.

The next ~M~ lines will each contain two integers, ~a_j, b_j~ ~(1 \le a_j, b_j \le N)~, denoting nodes ~a_j~ and ~b_j~ are connected by an edge in graph ~T~. There may be self-loops and duplicate edges between two nodes.

Output Specification

Output 1 if graphs ~S~ and ~T~ are isomorphic. Otherwise, output 0.

Sample Input

5 4
1 2
2 3
3 4
4 5
5 4
4 3
3 2
2 1

Sample Output

1