I passed all test cases mentioned in the discussion.

There are 4 tests in my algorithm:
- is there a loop (from M and N) ?
- is the graph connected ?
- is there a cycle?
- for each component of the graph:
  find the longest path and compare the length with S

any hint?

Edited by author 06.09.2017 11:02

Edited by author 06.09.2017 11:02

i had problems with 3rd test case. this input should help you:
1 1 5
1 1 2

the key here was to look closely at restrictions:
1 ≤ M ≤ 100; 1 ≤ N ≤ 10 000

assuming there could not be several ways from different x and y, and no loops from x to x, there should be at most 4950 connections between cities

3rd test contains road from X to X, so answer is "YES"