개구리 2

연못에 개구리가 앉을 수 있는 연꽃이 $N$개 있고, 연꽃 사이를 잇는 다리 역할의 통나무가 $M$개 있다. 같은 연꽃 쌍을 잇는 통나무는 많아야 1개다. 여기에 개구리 $N$마리가 각각 연꽃 하나에서 쉬려고 한다. 한 연꽃에는 개구리가 한 마리만 앉으므로, 배치가 끝나면 모든 연꽃에 개구리가 한 마리씩 앉아 있다.

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

통나무마다 대화 주제가 하나씩 정해져 있다. 그 주제에 대한 두 개구리의 흥미도가 같으면 대화가 이루어지고, 다르면 이루어지지 않는다.

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

개구리를 적절히 배치해 모든 통나무에서 정해진 주제로 대화가 가능한지 판정하고, 가능하면 그 배치를 구하는 프로그램을 작성하여라.

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

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

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

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

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

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

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