YingHua is a professor of computer science. She is teaching graph theory course.

For a given graph G(V,E), YingHua adhered n labels on those vertices, one label for one vertex, which is 1, 2, …, n, respectively.

YingHua has a naughty monkey Tom. Tom took off all n labels on those graph and adhered them back in a random order, also one label for one vertex. It was unknown if Tom changed the edges of the graph.

Now Yinghua wants to know whether the edges are same as before. Maybe you can help her by programming. (If you can not judge difference, you should think they are same.)

The first line of input is an integer k, which is the number of cases. The following 3k lines contain k case.

In each case, the first line contains two integer N and E, which are the number of vertices and the number of edges, where 1 <= N <= 25 and 1 <= E <= 100. The second line are E edges, i.e. the (2i-1)th and 2ith numbers are the labels of two vertexes one edge between. The third line is the status after Tom processed.

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

same
different