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 nonnegative integers <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.

---

hide comments

Previous  1  2 Next >

2012-12-30 15:19:18 Erik Lončarek The picture he meant to provide: Last edit: 2012-12-30 15:26:05

2012-05-07 20:15:34 Goran Zuzic I see a lot of people have some problem understanding the problem, so I'll clarify it the way I've seen it: Mirko once, while travelling from 0 to 1, wrote every label that he saw when he traversed an edge to a notebook in order. He repeated the process another time and found out that the two sequences were identical. Is it possible that the routes he took on the two occasions weren't identical?

2012-04-12 19:00:50 sava Do we have to pass all edges with same label???

2012-04-04 20:34:56 Nguyên Is it possible that a walk contains repeated node? For ex: 0-2-3-0-1

2012-04-02 01:30:25 Rita Cristian Last edit: 2012-04-02 01:34:04

2012-01-03 16:54:55 Radu Grigore @ebd: "Repeated" edges are distinct edges, yes. @Aleksa: I don't understand the question.

2011-06-27 13:33:55 Aleksa Can valid path consist of different labelled edges?

2010-03-18 01:12:26 ebd Are repeated edges considered distinct? What is the answer for: 2 2 0 1 0 0 1 0?

2009-10-02 00:14:25 Radu Grigore Right. Thanks Adrian!

2009-10-02 00: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.