VM7WC '16 #3 Silver - Can Shahir even get there?!

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M

Problem type

Shahir was already taped shut in the box when it occurred to him that he didn't know if it was possible to get from his house to his prom date's. That's no problem: he asks one of the friends that will deliver him, Dhruvit, to check.

There are N houses in Shahir's neighbourhood and M roads that connect those N houses. Each road connects two houses. All roads can be traveled down both directions. Each house is distinctly numbered and identified by a number in the range 1 \dots N.

Shahir lives in house A. His date lives in house B. Is there a path of roads to follow such that Dhruvit can drive the packaged Shahir from house A to house B? Dhruvit wrote (and you, vicariously, will write) a program to answer that question.

Input Specification

The first line will contain four integers, separated by spaces:

  • N (1 \le N \le 2\,000): The number of houses in Shahir's neighbourhood.
  • M (0 \le M \le 2\,000): The number of roads in Shahir's neighbourhood.
  • A (1 \le A \le N): Shahir lives in house A.
  • B (1 \le B \le N): Shahir's date lives in house B.

The next M lines contain two space-separated integers X and Y (1 \le X, Y \le N), denoting a road that connects house X with house Y. Two roads will never connect the same two houses.

Output Specification

On a single line, print GO SHAHIR! if Shahir can make it to his date's house. Otherwise, print NO SHAHIR!.

Sample Input 1

6 7 1 6
1 2
2 3
2 5
5 1
3 4
4 5
4 6

Sample Output 1


Explanation for Sample 1

Here is the graph of Shahir's neighbourhood:

Shahir's house is house 1. His date's house is at house 6. Dhruvit can drive Jeffrey from houses 1 to 6 by following the path 1 \to 2 \to 3 \to 4 \to 6 or 1 \to 5 \to 4 \to 6.

Sample Input 2

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

Sample Output 2


Explanation for Sample 2

This map of Shahir's neighbourhood is the same as the one in Sample 1, but the edge between houses 4 and 6 is removed. As a result, Dhruvit can no longer drive Shahir to his date's house.


  • 0
    JohnQing  commented on Dec. 1, 2021, 10:24 a.m.

    I'm getting WA on #3, 9 and 10 and I have absolutely no idea how to continue. Anyone have any tips on what cases I should consider?

  • 5
    ryanawad  commented on Nov. 24, 2021, 2:30 p.m.

    This is a great problem for an introduction to graph theory

  • 6
    pgupta1  commented on Jan. 25, 2021, 6:05 p.m.

    Hi, I don't know why my code got WA on all the test cases but it seems to work fine on the sample inputs. Here is a link to my submission Code

    • 9
      julian33  commented on Jan. 25, 2021, 6:22 p.m.

      You spelt shahir wrong.

      • 18
        pgupta1  commented on Jan. 25, 2021, 7:08 p.m.

        Thank you. It works now, that was pretty embarrassing.

        • 0
          planT_444  commented on Aug. 17, 2021, 9:08 a.m.

          i did the same thing lol

  • 1
    anthonypirvuti  commented on May 24, 2020, 2:52 p.m.

    I always get case #5 wrong so how would I go about checking for corner cases

    • 7
      sjay05  commented on May 24, 2020, 3:21 p.m.

      Think what your program might output if A = B.

  • -10
    nabil_boudraa38  commented on Feb. 18, 2019, 6:36 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

    • 16
      TimothyW553  commented on Feb. 18, 2019, 8:17 p.m.

      a road is bidirectional

  • 2
    LunarCoffee  commented on Nov. 8, 2018, 9:40 p.m.

    I'm getting segfaults and bad_alloc for all the test cases. The segfaults might be from indexing arrays out of bounds, but I'm not sure why I'm getting bad_alloc, considering I don't use any dynamically allocated memory with new. I'm not quite sure what's going on...

  • 5
    Kirito  commented on Oct. 4, 2017, 10:12 a.m.

    Note that even though the first sample case has M > N, the actual test data has M \leq N.

  • -24
    u_yousafzai54  commented on July 1, 2017, 10:05 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.

  • 2
    odaniel  commented on Jan. 23, 2016, 7:19 p.m. edited

    I keep getting WA on #5. I'm probably in the wrong here, but I'm just checking as I'm the only Python 2 submission, and I have gotten the short end of the data precision stick before...

    EDIT: Nevermind, corner cases are my life! Thanks all!

    • 5
      Vincent  commented on Feb. 11, 2016, 9:49 a.m.

      yes there is a problem, you have to check all of the corner cases.