AMBIG - Words on graphs

Input

The input is a directed (multi)graph.

The first line gives the number of edges M and the number of nodes N (>=2). Then each edge is described by a line of the form "FROM TO LABEL". Nodes (FROM, TO) are numbers in the range 0 .. N-1 and labels are also numbers.

All numbers in the input are non-negative integers less then 2000.

Output

Print "YES" if there are two distinct walks with the same labelling from node 0 to node 1, otherwise print "NO".

Example 1

Input:
4 4
0 2 0
0 3 0
2 1 1
3 1 2

Output:

NO

Example 2

Input:
10 9
0 2 0
2 1 0
2 3 0
3 4 0
4 2 0
2 5 0
5 6 0
6 7 0
7 8 0
8 2 0

Output:

YES

In this case the shortest labelling that appears on two walks is 0 repeated 10 times.

drawing of example 2


Added by:Radu Grigore
Date:2009-09-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL GOSU NODEJS PERL6 VB.NET
Resource:S Even, On Information Lossless Automata of Finite Order, 1965

hide comments
2011-06-27 11:33:55 Aleksa
Can valid path consist of different labelled edges?
2010-03-18 00:12:26 ebd
Are repeated edges considered distinct? What is the answer for: 2 2 0 1 0 0 1 0?
2009-10-01 22:14:25 Radu Grigore
Right. Thanks Adrian!
2009-10-01 22:14:25 Adrian Satja Kurdija
"In this case the shortest labelling that appears on two walks is 0 repeated 17 times."

I think it's not 17 but 10 times. One walk would be
0-2-3-4-2-5-6-7-8-2-1
and the second would be
0-2-5-6-7-8-2-3-4-2-1.
2009-10-01 22:14:25 Radu Grigore
Please let me know here http://www.spoj.pl/forum/viewtopic.php?f=29&t=6008&sid=76af1ddb393c37d56832b77b77af06ce of a better way to put pictures in problem statements.
2009-10-01 22:14:25 piyifan
In China mainland, I can't see the image from blogspot.
2009-10-01 22:14:25 Radu Grigore
By "distinct" I meant "not the same". Would "different" be better?
2009-10-01 22:14:25 [Trichromatic] XilinX
Does "two distinct walks" mean "two routes which don't share any edge"?

Last edit: 2009-09-30 05:16:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.