7574: [CSES Problem Set] Cycle Finding
[Creator : ]
Description
You are given a directed graph, and your task is to find out if it contains a negative cycle, and also give an example of such a cycle.
Input
The first input line has two integers $n$ and $m$: the number of nodes and edges. The nodes are numbered $1,2,\ldots,n$.
After this, the input has $m$ lines describing the edges. Each line has three integers $a, b, c$: there is an edge from node $a$ to node $b$ whose length is $c$.
After this, the input has $m$ lines describing the edges. Each line has three integers $a, b, c$: there is an edge from node $a$ to node $b$ whose length is $c$.
Output
If the graph contains a negative cycle, print first "YES", and then the nodes in the cycle in their correct order.
If there are several negative cycles, you can print any of them.
If there are no negative cycles, print "NO".
If there are several negative cycles, you can print any of them.
If there are no negative cycles, print "NO".
Constraints
$1≤n≤2500$
$1 \le m \le 5000$
$1 \le a,b \le n$
$-10^9 \le c \le 10^9$
$1 \le m \le 5000$
$1 \le a,b \le n$
$-10^9 \le c \le 10^9$
Sample 1 Input
4 5
1 2 1
2 4 1
3 1 1
4 1 -3
4 3 -2
Sample 1 Output
YES
1 2 4 1