Problem2: Magic Doorway Sophie has found herself in a bit of a pickle. While exploring the woods behind her house, she stumbled across a magic doorway that transported her to a mystical new land. Immediately after depositing her in this new world however, the doorway disappeared leaving Sophie stranded. Hearing Sophie's cries of distress, a kind elf comes to offer his assistance. He explains to her that the doorway's disappearance is not permanent. It appears every hour at one of n different location, and it doesn't reappear at a location until it has appeared at all n locations. There is also one caveat: the doorway is attuned to her desire to find it, and the strength of her perseverance, so once she starts seeking it, she is not allowed to stop anywhere with the intention of waiting to catch the doorway nearby. If she should stop traveling while seeking it, the sequence of destined locations for the doorway will be completely rearranged, and she will have to start her quest all over. So Sophie must arrive at its location just as it is opening up. By reading her mood at the start of her journey, the elfis able to predict the exact sequence of appearances of the doorway, which he is willing to provide her with. As one would expect, the first location on his list is never the same as Sophie's starting location (otherwise, where would be the test of perseverance?). The elf draws her a map, showing the n locations and indicates the pairs between which she would be able to travel within an hour. There are a total of m such pairs. He also presents her with the complete sequence of the next n locations where the doorway is scheduled to appear Given the information provided by the elf, and her starting location, s, help Sophie to determine the earliest time and location where she can catch the doorway opening up, without ever being in the same location in two consecutive hours. Input Format The first line contains the three space separated integers n ms The second line contains n space separated integers, po, Pr..pn-1, indicating that the doorway will open at location pi at exactly i hours after Sophie starts travelling. The following m lines will each contain two space separated integers ui and vi, for 1