   Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Katu Puzzle
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14426 Accepted: 5272

Description

Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 ≤ c ≤ 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 ≤ Xi ≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:

Xa op Xb = c

The calculating rules are:

 AND 0 1 0 0 0 1 0 1
 OR 0 1 0 0 1 1 1 1
 XOR 0 1 0 0 1 1 1 0

Given a Katu Puzzle, your task is to determine whether it is solvable.

Input

The first line contains two integers N (1 ≤ N ≤ 1000) and M,(0 ≤ M ≤ 1,000,000) indicating the number of vertices and edges.
The following M lines contain three integers a (0 ≤ a < N), b(0 ≤ b < N), c and an operator op each, describing the edges.

Output

Output a line containing "YES" or "NO".

Sample Input

```4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR```

Sample Output

`YES`

Hint

X0 = 1, X1 = 1, X2 = 0, X3 = 1.

Source

[Submit]   [Go Back]   [Status]   [Discuss] Home Page Go Back To top