연금술

문제

ANA 길드에서 '연금술'을 수강 중인 견습 연금술사 차차는 어려운 과제에 직면했다. 과제의 내용은 다음과 같다.

총 $N$종류의 재료가 있으며, 이 중 $M$종류의 재료는 이미 충분히 주어져 있다. 나머지 모든 재료는 연금술 조합식을 이용해 만들어야 하며, 모든 재료 $N$종을 완성해 제출해야 과제를 통과할 수 있다.

주어진 $M$종류의 재료는 필요한 만큼 무한히 사용할 수 있으며, 연금술 외의 다른 방법은 사용할 수 없다. 따라서 차차는 자신이 알고 있는 연금술 지식을 총동원해 과제를 해결하려 한다.

차차가 알고 있는 조합식은 총 $K$개다. 각 조합식은 $2$개의 재료를 사용하며, 같은 재료를 두 번 사용하는 것도 가능하다. 하나의 조합식을 사용하면 특정한 재료 하나를 새롭게 생성할 수 있다.

차차는 이러한 조합식을 적절히 활용하여, 모든 재료를 적어도 하나 이상 만들 수 있을까?

입력

첫째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(1 \le M \le N \le 1,000; 1 \le K \le 1,000)$

둘째 줄에 길이 $N$의 정수 배열 $A$가 공백으로 구분되어 주어진다. $A_i = 1$이면 $i$번 재료는 주어진 재료이고, $A_i = 0$이면 조합식을 통해 만들어야 하는 재료이다. $(A_i \in \{0, 1\}; \sum_{i=1}^{N} A_i = M)$

이후 $K$개의 줄에는 조합식이 주어진다. 각 줄에는 세 정수 $X_1$, $X_2$, $Y$가 공백으로 구분되어 주어진다.

$X_1$번 재료와 $X_2$번 재료를 사용하면 $Y$번 재료를 만들 수 있다는 뜻이다. $(1 \le X_1 \le N; 1 \le X_2 \le N; 1 \le Y \le N)$

출력

모든 종류의 재료를 만들어 과제 해결이 가능하다면 yes, 불가능하다면 no를 출력한다.

예제 입력 1

5 3 6
1 0 1 0 1
1 3 5
2 3 4
1 2 4
3 4 2
3 5 2
4 5 1

예제 출력 1

yes

예제 입력 2

4 1 4
1 0 0 0
1 2 3
2 3 4
3 4 1
1 4 2

예제 출력 2

no