개구리 3

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

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

통나무마다 대화 주제가 한 개 정해져 있고, 그 주제의 흥미도가 두 개구리에서 같을 때만 대화가 이루어진다.

또 개구리마다 선호하는 연꽃이 한 개 또는 두 개 있다. 선호하지 않는 연꽃에서는 불만을 품고 난장판을 만들므로, 모든 개구리는 자기가 선호하는 연꽃에 앉아야 한다.

모든 통나무에서 정해진 주제로 대화가 가능하도록 개구리를 배치할 수 있는지 판정하고, 가능하면 그 배치를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$과 $M$이 주어진다. ($1 \le N \le 3000$, $0 \le M \le \min(N(N-1)/2,\ 5 \times 10^5)$)

다음 $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$, $A \ne B$, $1 \le T \le 4$) $A$번 연꽃과 $B$번 연꽃을 잇는 통나무가 있고 그 통나무의 대화 주제가 $T$번째 주제라는 뜻이다. 주제는 음식, 취미, 가족, 철학 순으로 번호를 매긴다.

가능한 배치가 있으면 첫째 줄에 YES를 출력한다. 둘째 줄에는 1번 연꽃부터 $N$번 연꽃까지 각 연꽃에 앉는 개구리의 번호를 공백으로 구분해 출력한다. 배치가 여러 가지면 이 수열이 사전순으로 가장 앞서는 것을 출력한다.

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