MWC '15 #4 P4: Dealing with Knots

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

MathBunny123 needs string for his physics ISP. However, the string he has is a huge mess, it's stuck together and a lot of it is tangled (there are many different pieces). Luckily he has the legendary TangledStringAnalyzer9000. This revolutionary machine can scan the mess, assign each piece of string a number, and tell him which pairs of string are connected! MathBunny123 wants to check if string A is tangled with string B; your job is to tell him if those two pieces of string are connected to each other by any means (if string A is connected to other pieces of string and one or many of those are connected to B, then A is still tangled with string B). His string is in such a mess that he managed to make the connections one way; they do not reciprocate.

Input Specification

The first line of input will contain the number of analyzed connections or number of pieces of string, N (1 \le N \le 1000).

The next N lines of input will contain the connection in the form, a b, where a is the first string, b is the second string. 1 \le a,b \le 1000.

The last line of input will be in the form, X Y, the pair of string pieces which will be checked to see if they are tangled or not. Each piece of string, a, will only appear once as the first piece of string in a connection, a b.

Output Specification

Output Tangled if string A is connected to string B, otherwise output Not Tangled.

Sample Input

3
1 2
2 3
3 1
3 2

Sample Output

Tangled

Comments


  • 2
    Ninjaclasher  commented on Oct. 20, 2017, 10:57 a.m. edited

    Shouldn't (1 \le a, b \le N) and not (1 \le a, b \le 1000)? Or am I not understanding the problem correctly?

    Also:

    Each piece of string, aa, will only appear once as the first piece of string in a connection, a b.

    Doesn't sample case 1 violate this? Two connections start from 3.


    • 3
      injust  commented on Oct. 20, 2017, 12:48 p.m.

      The last line of input specifies the two pieces of string to be checked


  • 1
    Daniel123  commented on April 17, 2016, 3:45 p.m. edit 4

    5 1 2 2 3 3 4 4 5 5 3 1 5


    • 2
      r3mark  commented on April 17, 2016, 4:01 p.m.

      Tangled