Frog 3

A pond has $N$ lotus pads that frogs can sit on and $M$ logs that join pads and work as bridges. At most one log joins any given pair of pads. $N$ frogs each want to rest on one pad, and one pad holds 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, and philosophy. Every frog has an interest level from 1 to 5 for each topic.

Each log carries one fixed topic. The conversation happens only when the two frogs have the same interest level for that topic.

Each frog also prefers one or two pads. On any other pad it turns unhappy and wrecks the place, so every frog must sit on a pad it prefers.

Write a program that decides whether the frogs can be placed so that every log allows a conversation on its topic, and that reports such a placement when one exists.

The first line contains $N$ and $M$. ($1 \le N \le 3000$, $0 \le M \le \min(N(N-1)/2,\ 5 \times 10^5)$)

Each of the next $N$ lines contains four integers, the interest levels of one frog for food, hobbies, family, and philosophy in that order. Each integer is between 1 and 5. The $i$-th of these lines describes frog $i$.

Each of the next $N$ lines contains the numbers $A$ and $B$ of the pads one frog prefers. ($1 \le A, B \le N$) A frog that prefers a single pad is given with $A = B$. The $i$-th of these lines describes frog $i$.

Each of the last $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 topic is topic $T$. The topics are numbered in the order food, hobbies, family, philosophy.

If a placement exists, print YES on the first line. On the second line print the number of the frog placed on pad $1$, then pad $2$, and so on up to pad $N$, separated by spaces. When several placements work, print the one whose sequence is lexicographically smallest.

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