All Tracks Algorithms Graphs Maximum flow Problem

New Friends
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

New year has come and Anuj has moved to a new city "Treapland". Now he made some new friends and they started playing a game. Treapland has a very large area with various small cities within it numbered from $$1$$ to $$N$$ connected through some directed roads. Anuj has $$K$$ friends. The game consists of the condition that they have to reach the city $$b$$ from city $$a$$ such that the paths are not overlapped anywhere i.e. all the friends reach city $$b$$ from city $$a$$ through different roads. You have to print YES if they will be succesfully able to play the game and NO if not
Note:Read the sample test case carefully
Input
First line contains $$t$$ as input denoting total number of the test cases. Each testcase contains some data as input. The first line of each test case is $$N$$ and $$R$$ where $$N$$ is total number of cities and $$R$$ is the total roads connecting them. Next R lines contains pair of integers u and v which means there is a directed edge from node u to v. Next line of the test case contains three numbers $$a$$,$$b$$ and $$k$$ where $$a$$ is the starting city, $$b$$ is the ending city and $$k$$ is total number of friends.
Output
Print YES if game can be played else print NO
Constraints
$$1\le t\le 10$$
$$2\le N \le 150$$
$$2\le R \le 10000 $$
$$1\le K \le 500$$
$$1\le u , v \le N$$

SAMPLE INPUT
1
5 4
1 2
2 3
3 4
4 5
1 5 2
SAMPLE OUTPUT
NO
Explanation

Since there is only 1 path between the starting city and ending city so they wont be able to play the game

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

IIIT Jabalpur

Challenge Name

CodeRing - III

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications