文理学院程序设计在线练习


Special Graph Isomorphism

Time Limit: 2 Second(s)    Memory Limit: 256 MB

Total Submission(s): 0   Accepted Submission(s): 0
Problem Description

You are given two special graphs with equal number of vertices and edges, and both of two graphs satisfy the following restrictions:
1.Contain n identical unweighted vertices, numbered from 1 to n.
2.Contain m undirected unweighted edges.
3.The degree of any vertex is 2.
Please check if these two graphs are isomorphic.

If you don’t understand the definition of Graph Isomorphism, please read the information given below:
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f: V(G)->V(H) such that any two vertices u and v of G are adjacent in G if and only if f(u) and f(v) are adjacent in H. The following picture shows a pair of isomorphic graphs:


Input

The first line of data is the number of test cases T.
The first line of each test case contains two integers n and m, which represent the number of the vertices and edges. Then 2m lines follow, which show the information of the two graphs, first m lines are about the graph 1, next m lines are about the graph 2. Each line contains two integers u, v, represent an edge connecting vertex u and v.
T <= 100
1 <= n,m <= 100000
Sigma(n),Sigma(m)<=2e6
1 <= u,v <= n

Output

For each test case print one line, if the graphs are isomorphic print ‘YES’, else print ‘NO’ (without quotes).

Sample Input
1
3 3
1 2
2 3
3 1
1 3
1 2
2 3
Sample Output
YES
Hint

We guarantee that the graphs are legal.
And you are supposed to use scanf because of the large amount of input data.

Source

2019绍兴市计算机技能竞赛