Server Time: Wed Sep 23, 2020 7:30 am
Welcome ( logout
C - Similar Trees
  PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

Given two trees, you have to find whether they are same or not. A tree is a connected graph with no cycles.

In this problem a tree is described as a sequence of zeroes and ones. Initially you are on the root of the tree. If you get a 1, you declare a new node and you go to that node. The parent node of this node is the node you came from. If you get a 0, you will return back to its parent node. The trees will be given such that after traversing all the nodes, you will return back to the root.

The given tree can be described in two ways.

1. 1011010100

2. 1101010010

In this problem you are given two trees. You have to determine whether they are same or not. Two trees will be same if we start from their roots, we will get same shaped trees.


Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case contains two lines. In each line, a string will be given as a tree configuration. You can safely assume that the trees are valid and the length of any string will be between 0 and 10000 (inclusive). You can assume that the length of both the trees will be same.


For each case print the case number and 'Same' or 'Different' depending on whether the trees are same or not.

Sample Input

Output for Sample Input








Case 1: Same

Case 2: Same

Case 3: Different


Problem Setter: Jane Alam Jan
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan