Frog placement

A pond has $N$ lily pads that frogs can sit on, and $M$ logs that bridge pairs of pads. At most one log joins any given pair of pads. In this pond $N$ frogs want to rest, one frog on one pad.

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

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

Every frog also prefers one or two pads. A frog seated on a pad it does not prefer becomes unhappy and wrecks the place, so every frog has to sit on a pad it prefers.

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

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

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

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

Each of the next $M$ lines has three integers $A$, $B$, $T$. ($1 \le A, B \le N$, $1 \le T \le 4$) A log joins pad $A$ and pad $B$, and the topic of that log 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 the number of the frog seated on pad 1, then pad 2, and so on up to pad $N$, separated by spaces.

If several placements are valid, print only the lexicographically smallest of these sequences of $N$ numbers. That is, choose the placement whose frog on pad 1 has the smallest number, and among those the placement whose frog on pad 2 has the smallest number, and so on.

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