Frogs 2

A pond has $N$ lily pads that frogs can sit on and $M$ logs that act as bridges between pads. At most one log connects any given pair of pads. $N$ frogs want to rest, one frog per pad, so after the placement every pad holds exactly one frog.

Two frogs on pads joined by a log must be able to talk, otherwise they quarrel. There are four conversation topics: food, hobbies, family, philosophy. Every frog has an interest level from 1 to 5 for each topic.

Each log has one fixed topic. The two frogs it joins can talk when their interest levels for that topic are equal, and cannot talk when the levels differ.

Every frog also prefers 1 or 2 pads. A frog placed on a pad it does not prefer gets upset and wrecks the place, so every frog must go to a pad it prefers.

Write a program that decides whether the frogs can be placed so that a conversation happens on every log with that log's topic, and that reports the placement when one exists.

The first line contains $N$ and $M$. ($1 \le N \le 100$, $0 \le M \le \min(N(N-1)/2, 1000)$)

Each of the next $N$ lines contains four integers, the interest levels of frogs 1 through $N$ in food, hobbies, family, and philosophy. Each integer is between 1 and 5.

Each of the next $N$ lines contains the pad numbers $A$ and $B$ preferred by frogs 1 through $N$. ($1 \le A, B \le N$) A frog that prefers only one pad is given with $A = B$.

Each of the next $M$ lines contains three integers $A$, $B$, and $T$. ($1 \le A, B \le N$, $A \ne B$, $1 \le T \le 4$) A log joins pad $A$ and pad $B$, and its conversation topic is topic $T$. The topics are numbered in the order food, hobbies, family, philosophy.

If a valid placement exists, print YES on the first line. On the second line print, separated by spaces, the number of the frog placed on pad 1 through pad $N$.

If several placements are valid, only the lexicographically smallest sequence counts as correct. Choose the placement whose frog on pad 1 has the smallest number, break ties by the frog on pad 2, and so on.

If no valid placement exists, print NO on the first line.