Company: Walmart sparkplug
Difficulty: medium
Thief and Police There are N buildings numbered from 0 to N-1. Among them there is a thief hiding in one of the building and there is a police in one of the building. You have to find if it's possible to catch the thief. Thief can only escape from the police if: Thief is a part of a cycle length 4 or more If there is no path from a police to the thief If there is a cycle in the graph with a length of 4 or more and thief can reach the cycle quicker than a police. Input Format The first line contains four space-separated integers N, T, P and M denoting: N: the number of buildings T: the starting position of thief P: the starting position of police M: the number of connections between buildings The next M lines contain X and Y where X and Y defines there is connection between building X and Y. Output Format If police is able to catch the thief output "YES", Otherwise "NO". Constraints 0 ≤ X, Y Sample Test Case 1 Input: 4 0 2 4 0 1 1 2 2 3 3 0 Output: NO The graph forms a cycle of length 4