[Login|Register]
Problems

Status

Rank

Problem 1119
Graph
Time Limit: 1000ms
Memory Limit: 65536kb
Description

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.)

Input

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.

Output
If the relation of edges is same, output “same”, else output “different”.
Sample Input
2
3 2
1 2 2 3
1 3 3 2
2 2
1 2 1 2
1 1 2 2
Sample Output
same
different
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.4ms with 1 query(s).