Busy Beaver는 MIT에 입학하려고 합니다. SAT 시험을 치르는 대신, 그는 더 나은 방법, 즉 세 배 더 나은 방법으로 3-SAT 문제를 해결하기로 했습니다! 그는 정말 놀라운 해결책을 찾아냈지만, 불행히도 지원서의 여백이 너무 좁아 그 해결책을 다 적을 수 없었습니다. 그래서 그는 자신만의 문제 버전을 만들었지만, 이를 해결하기 위해 여러분의 도움이 필요합니다.

$n, m$을 양의 정수라고 합시다. $\{0, 1\}$의 값을 가지는 $n$개의 변수 $x_1, \dots, x_n$이 있습니다. 절(clause)은 $1 \le a \le b \le c \le n$인 인덱스를 가진 세 변수의 곱 $x_a \cdot x_b \cdot x_c$입니다. 여러분은 이러한 절 $m$개의 합으로 이루어진 식을 받습니다. 예를 들어, 4개의 변수와 3개의 절로 이루어진 식은 다음과 같을 수 있습니다.

$$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_3 \cdot x_4 + x_2 \cdot x_3 \cdot x_4$$

결과 식을 홀수로 만드는 $x_1, \dots, x_n$의 값을 선택할 수 있는지 결정하십시오.

입력

각 테스트는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 10^5$)가 주어집니다.

그다음 테스트 케이스들에 대한 설명이 이어집니다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $n, m$ ($1 \le n, m \le 10^5$)이 주어집니다.

각 테스트 케이스의 다음 $m$줄은 합에 포함된 각 절을 설명합니다. $i$번째 줄은 세 개의 공백으로 구분된 정수 $a_i, b_i, c_i$ ($1 \le a_i \le b_i \le c_i \le n$)로 구성되며, 이는 합의 $i$번째 절이 $x_{a_i} \cdot x_{b_i} \cdot x_{c_i}$임을 나타냅니다.

모든 테스트 케이스에 대해 $n$의 합과 $m$의 합은 $10^5$를 넘지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해, 식을 홀수로 만드는 $x_i$ 설정이 존재하면 첫 번째 줄에 YES를 출력하고, 그렇지 않으면 NO를 출력하십시오. 각 문자는 대소문자를 구분하지 않습니다. 예를 들어, yes, Yes, YeS 모두 긍정적인 답변으로 인식됩니다.

그 후, YES라고 응답했다면, 식을 홀수로 만드는 $x_1, \dots, x_n$ ($x_i = 0$ 또는 $1$)을 공백으로 구분하여 두 번째 줄에 출력하십시오. 가능한 해가 여러 개라면, 그중 아무거나 출력해도 됩니다.

서브태스크

각 서브태스크에서 YES/NO 응답이 정확하면 점수의 50%를 받으며, 제공된 $x_i$ 값이 정확해야 나머지 점수를 받을 수 있습니다. 부분 점수를 받기 위해서는 각 테스트 케이스마다 정확히 $n$개의 $x_i$ 값을 출력해야 합니다.

• (50점): 각 절 내에서 변수는 한 번만 나타납니다. 즉, $a_i < b_i < c_i$입니다.
• (50점): 추가 제약 조건이 없습니다.

예제

입력 1

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

출력 1

YES
1 1 1 1
NO

참고

첫 번째 테스트 케이스는 문제 설명의 예시와 동일합니다. 이 식에서 모든 변수를 1로 설정하면 식의 값은 $1 + 1 + 1 = 3$이 되며, 이는 홀수입니다.

두 번째 테스트 케이스에서 주어진 식은 $x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$입니다. $x_1, x_2, x_3$를 어떻게 설정하더라도 이 식을 홀수로 만들 수 없음이 증명될 수 있습니다.