Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3679
One Touch Drawing

Time Limit: 2 Seconds      Memory Limit: 65536 KB

These days, Alex is fond of a mobile game called "one touch drawing".

Alex is given a graph, and requires him to travel all the edges of the graph certain times. To make the game funny, some regulations are added to this game.

  • First, all the edges are required to be travelled for once or twice.
  • Second, there will be some pairs of transport vertices. For example, s1 and s2 are a pair of transport vertices. Once Alex travels to s1, then he will be forced to arrive at s2, and the transportation is directed!
  • Third, most of the edges are undirected, while the others are directed. A directed edge may have one Green Vertex. Once Alex travels to a Green Vertex, the direction of those edges whose Green Vertex is that vertex will change.
Unfortunately, when Alex played the game, he found some of the graph couldn't be drawn with these contraints. Alex doesn't want to waste time on playing on those graph without any solutions. So he asks you to tell him if the graph given by the game has any solution.

Input

The input contains less than 30 test cases. NOTICE that's no empty line between each test case. For each test case, first line has three numbers N (1 ≤ N ≤ 12) - the number of vertices, M (1 ≤ M ≤ 10) - the number of edges, W(0 ≤ W ≤ N / 2) - the number of pairs of transport vertices. The following M lines, each line contains five integers x, y, ti, d, z.(0 ≤ x, y ≤ N - 1)

  • t : edge(x, y) is required to travel for ti times.(ti = 1 or ti = 2), (We promise the sum of ti(1 ≤ i ≤ M) is no more than 10!)
  • d : d = 0 means edge (x, y) is undirected; d = 1 means the original direction of edge(x, y) is x -> y. (d = 0 or d = 1)
  • z : the index (0... N - 1) of the Green Vertex of edge(x, y). If (x, y) is undirected or does not have a Green Vertex, then z = -1; (-1 ≤ z ≤ N - 1)
Last followed by W lines. Each line contain two integers s1 and s2. Means s1 and s2 are a pair of tranport vertices(and the transport direction is s1 -> s2 ONLY!). We promise that s1 can only transport to ONE vertice. Process to END_OF_FILE.

Output

For each test case. Output one line.If there exists a solution for that graph, output "Yes". Otherwise, Output "No".

Sample Input

4 5 1
0 1 1 0 -1
0 3 1 0 -1
1 2 2 0 -1
2 3 2 0 -1
0 2 1 1 2
1 3
4 3 0
0 1 1 0 -1
0 2 1 0 -1
0 3 1 0 -1

Sample Output

Yes
No

Hint

The solution of first sample input is 0 -> 1, 3 -> 2 -> 1, 3 -> 2 -> 1, 3 -> 0 -> 2.


Author: GUO, Tingxin
Contest: ZOJ Monthly, January 2013
Submit    Status