All submissions for this problem are available.
In the present world, Operating System is one of the most important tool. Its a big business and a lot of profit is generated by the operating system developers depending on the features they have implemented in their OS, which are demanded/required by the users. In one such instance, an operating system developer IOPC (International Operating Product Creators) developed a special type of operating system for their users.
Their operating system had the following structure: The user is initially given a root directory, and the user is allowed to create new directories. Every time he creates a new directory, he must create a link between the new one and exactly one of the existing directories making sure that the new directory is accessible from the root directory. This structure gave them special features like there is only one way to move from one directory to another directory through the links created. For ease of debugging, they named their directories with integer values.
Their product created a new revolution in the market. However, in a short time, another operating system developer Copycat Operating Systems (CCOS) launched a very similar OS with exactly the same features. Although the OS manual of the new product in the market had different numbers assigned to their directories. But IOPC detected foul play and are convinced that CCOS have stolen their code and just made some minor changes in it and presented it as their own. Since, you are one of the top programmers in the world. They have asked for your help to resolve this issue.
After sufficient study, you have reached the conclusion that if the internal structure of the file system of two operating systems match after performing a certain set of operations on both of them, then they are the same. So, to ease your work, you have designed a test suite for this verification purpose. Your test contains performing some operations on both the operating systems and see what links are formed in each of the file systems. However, due to shortage of time, you forgot to ensure that the test suite performs the tests on both the operating systems in the same order. However, you are able to get the generated links and the root directory of the operating systems.
Given this information, you have to print whether the Copycat Operating Systems have actually copied from IOPC or they just got lucky in developing a similar system.
The first line of the input contains an integer T denoting the number of test cases. The description for each of the test cases starts from a new line. The first line of input for each test case contains an integer N, the number of directories (including the root) generated in the file systems of both the OS by the test suite. Next, follow descriptions for the file system (root and links structure) for both the operating systems, one after the other, each beginning from a new line and each containing N lines. The first line for each of the OS, contains an integer R, the integer corresponding to the root. The next N-1 lines
describe the link structure with the ith line containing two space separated integers Ai Bi meaning that there’s a link between the directories with integer names Ai and Bi.
The output must contain as many lines as the number of test cases T. For each test case print 1 if both the operating systems generate structurally same file systems (root and link structure) of directories when operated upon by the test suite, otherwise print 0.
- T ≤ 3
- 1 ≤ N ≤ 10^5
- 0 ≤ Ai, Bi, R ≤ N-1 for 1 ≤ i ≤ N-1
Input: 1 2 0 0 1 0 1 0 Output: 1
This problem will be tested on Cube (Pentium G860 3GHz)
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions