[Login|Register]
Problems

Status

Rank

Problem 1117
Bean Language
Time Limit: 1000ms
Memory Limit: 65536kb
Description

In the year 2099, the people in Earth established diplomatic relations between aliens from Pegasus galaxy. The Pegasusan people developed a kind of language called Bean Language, the words of which are based on graphic symbols. In ancient times of Pegasus, the Pegasusan had no paper to write on.

So, they carved every word on one rigid bean, and they string these beans to form a sentence.

Every graph symbol on bean consists of a certain number of spots and edges connect between these spots. The number of edges is exactly the number of spots minus 1, but all the spots are connected. Two Beans have the same spots and edges relations are considered to be the same word.

However, after the Pegasusan invented paper, the word of Bean Language differentiated into various handwritings. But handwritings of the same word have the same spots and edges relations. Like the two graphics in the fellow figure, they are the same word carved on bean and written on paper. Pegasusian can recognize the two forms are identical in no time, because they are so familiar with their own language.

Now, the Pegasusan provide us a dictionary of their words. The problem is that the people on Earth cannot identify the Bean Language words handwritings in one sight, especially when the word is more complex. So, that is your job to recognize the given two symbols are the same word or not.

Input

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

In each case, the first line is an integer n, which is the number of spots of a bean word (2 <= n <= 1000). The second line is the connect relation of the word in Bean Language dictionary, and the third line is the connect relation of a word in handwriting.

Because all the spots in each word are labeled as 1, 2, ..., n, the connect relation is a list as u1, v1, u2, v2, ..., un-1, vn-1. ui and vi denotes the two endpoints of one edge without direction, and the edges have no order.

For example the connect relation of the word in the figure above is 1 2 3 1 4 3 3 5 and 1 2 3 5 1 3 1 4. They are in fact the same word.

Output
For each case, output “same” if the two words are the same Bean Language word, else output “different”.
Sample Input
2
5
1 2 3 1 4 3 3 5
1 2 3 5 1 3 1 4
4
1 2 2 3 2 4
2 1 2 3 3 4
Sample Output
same
different
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.1ms with 1 query(s).