개구리 배치

연못에 개구리가 앉을 수 있는 연꽃이 $N$개 있고, 연꽃과 연꽃을 잇는 다리 역할의 통나무가 $M$개 있다. 같은 연꽃 쌍을 잇는 통나무는 많아야 1개다. 이 연못에서 개구리 $N$마리가 각각 연꽃 하나에 앉아 쉬려고 한다.

통나무로 이어진 두 연꽃에 앉은 개구리는 다투지 않으려면 대화가 통해야 한다. 대화 주제는 음식, 취미, 가족, 철학 네 가지다. 개구리마다 각 주제의 흥미도가 1부터 5까지의 정수 하나로 정해져 있다.

통나무마다 대화 주제가 하나씩 정해져 있고, 그 주제의 흥미도가 양쪽 개구리에서 같아야 대화가 이루어진다.

또 개구리마다 선호하는 연꽃이 1개 또는 2개 있다. 선호하지 않는 연꽃에 앉으면 불만을 품고 난장판을 만들기 때문에, 모든 개구리는 자기가 선호하는 연꽃에 앉아야 한다.

개구리를 배치해 모든 통나무에서 정해진 주제로 대화가 이루어지게 할 수 있는지 판정하고, 가능하면 그 배치를 출력하는 프로그램을 작성하여라.

첫째 줄에 $N$과 $M$이 주어진다. ($1 \le N \le 15$, $0 \le M \le \min(N(N-1)/2, 100)$)

다음 $N$개의 줄에는 각 개구리의 음식, 취미, 가족, 철학에 대한 흥미도가 네 정수로 주어진다. 각 정수는 1 이상 5 이하다. 이 중 $i$번째 줄이 $i$번 개구리의 흥미도다.

다음 $N$개의 줄에는 각 개구리가 선호하는 연꽃의 번호 $A$와 $B$가 주어진다. ($1 \le A, B \le N$) 선호하는 연꽃이 하나뿐인 개구리는 $A = B$로 주어진다. 이 중 $i$번째 줄이 $i$번 개구리의 선호 연꽃이다.

다음 $M$개의 줄에는 세 정수 $A$, $B$, $T$가 주어진다. ($1 \le A, B \le N$, $1 \le T \le 4$) $A$번 연꽃과 $B$번 연꽃을 잇는 통나무가 있고, 그 통나무의 대화 주제가 $T$번째 주제라는 뜻이다. 주제 번호는 음식, 취미, 가족, 철학 순이다.

가능한 배치가 있으면 첫째 줄에 YES를 출력한다. 둘째 줄에는 1번 연꽃부터 $N$번 연꽃까지 각 연꽃에 앉을 개구리의 번호를 공백으로 구분해 출력한다.

가능한 배치가 여러 가지면 이 $N$개의 수를 앞에서부터 비교해 사전순으로 가장 앞서는 배치 하나만 출력한다. 즉 1번 연꽃에 앉는 개구리의 번호가 가장 작은 배치를 고르고, 그런 배치가 여럿이면 2번 연꽃에 앉는 개구리의 번호가 가장 작은 배치를 고르는 식으로 정한다.

가능한 배치가 없으면 첫째 줄에 NO를 출력한다.