CHAMPS - Michel and the championship


Michel is participating in a championship where each participant have pi (0<=i<=N-1) points. He knows for some pairs of participants an inequality between the points of each one, in the form pA -pB >= C. Now he wants to know if his data is correct, i.e., if its possible to assign points for each participant and satisfy all the inequalities.

Input

The input consists of several test cases (at most 150). The first line of each test case consists of two integers N and M (1<=N<=500, 0<=M<=5000). Then follow M lines of three integers A, B and C, indicating that pA -pB >= C (0<=A,B<=N-1, |C|<=20000).

Output

Print a single line for each test case with 'y' if the data is valid or 'n' if its not.

Example

Input
2 2
0 1 2
1 0 2
4 4
0 1 1
1 2 1
2 3 -2
3 0 1
4 4
0 1 1
1 2 1
2 3 -3
3 0 1

Output
n
n
y

hide comments
smso: 2018-08-05 08:12:39

got SIGSEGV, input may contain characters other than numbers, space and newline

Dario Sindicic: 2015-04-03 09:47:29

0<=A,B<=N-1
and yes EOF

Last edit: 2015-04-03 09:47:56
Akimil: 2015-04-02 22:42:35

What is the number of test cases? Until when we read?

Milan: 2015-04-02 01:21:21

I don't understand what is N supposed to do. Someone please explain me this part, thanks.

Last edit: 2015-04-02 01:23:37
Petar Bosnjak: 2015-04-01 18:20:57

We should read input till EOF?

Nikola: 2015-04-01 15:34:13

Can someone please explain this better with less conditions like: pA -pB >= C and 0<=A,B<=N-1, |C|<=20000?


Added by:Marcos Kawakami
Date:2012-02-19
Time limit:1.542s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Author: Guilherme Souza (guirns)