Number Of Paths :
Difficulty Level : Easy
Submissions : 751
Asked In :
Marks :10
: 13 | : 2
Hawking is a state containing N cities connected by M directed roads i.e. you can travel in only one direction. Linda challenged you and your K friends to start from a given city A and end their journey at city B without taking any road twice i.e. each friend travels on a unique path from A to B.
Task: Give whether you and your K friends will complete the challange or not, Print "YES" or "NO".
Constaints:
$$$1 \le T \le 10$$$
$$$2 \le N \le 150$$$
$$$1 \le M \le N*(N-1)$$$
$$$1 \le u, v \le N$$$
$$$1 \le K \le 500$$$
First line contains T, number of test cases.
First line of each test case contains N and M, number of cities and roads.
Next M lines contains two integers u and v denoting there is a road from u to v.
Next line contains A, B and K, the starting and ending city, and the number of friends.
For each test case, print "YES" or "NO" in a new line.
2 5 4 1 2 2 3 3 4 4 5 1 5 2 5 4 1 2 2 3 3 4 4 5 1 5 1
NO YES
1 6 12 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 4 5 4 6 3 5 1
YES
Sample Input:
1
5 4
1 2
2 3
3 4
4 5
1 5 2
Sample Output:
NO
Explanation:
Test Case 1: There is 1 path from 1 to 5, 1->2->3->4->5. So, 2 friends can't complete the challenge.
