예비 정비팀

철도망에는 $1$번부터 $M$번까지의 역이 있다. 역들은 $M-1$개의 선로로 연결되어 트리를 이룬다. 두 역 $u,v$ 사이의 단순 경로를 양 끝점을 포함하여 $P(u,v)$라 한다.

각 역에는 예비 정비팀이 한 팀씩 대기하고 있다. 정비팀이 공사에 투입되면 이후에는 다시 사용할 수 없다.

운영사는 $N$개의 공사를 순서대로 시작한다. 각 공사에는 기본안 $0$과 대체안 $1$이 있다. $i$번째 공사의 계획 $b$는 $(x_{i,b},u_{i,b},v_{i,b})$로 주어진다. 이 계획을 선택하면 $x_{i,b}$번 역의 팀을 투입하고 경로 $P(u_{i,b},v_{i,b})$를 비상 대응 구간으로 등록한다.

등록된 모든 비상 대응 구간에는 대기 중인 정비팀이 적어도 한 팀 있어야 한다. 계획은 다음 조건을 모두 만족할 때 실행할 수 있다.

• $x_{i,b}$번 역의 팀이 현재 대기 중이다.
• 해당 팀을 투입한 뒤에도 기존의 모든 비상 대응 구간에 대기 중인 팀이 남아 있다.
• 새 경로 $P(u_{i,b},v_{i,b})$에도 대기 중인 팀이 남아 있다.

각 공사에서는 기본안 $0$이 실행 가능하면 반드시 기본안 $0$을 선택한다. 기본안 $0$은 불가능하지만 대체안 $1$이 가능하면 대체안 $1$을 선택한다. 두 계획이 모두 불가능하면 해당 공사를 시작하기 직전에 전체 일정을 중단한다.

모든 공사를 시작할 수 있는지 판정하고 실제로 선택하는 계획들을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

각 테스트 케이스는 다음과 같은 형식으로 주어진다.

$M\ N$ $a_1\ b_1$ $a_2\ b_2$ $\vdots$ $a_{M-1}\ b_{M-1}$ $x_{1,0}\ u_{1,0}\ v_{1,0}\ x_{1,1}\ u_{1,1}\ v_{1,1}$ $x_{2,0}\ u_{2,0}\ v_{2,0}\ x_{2,1}\ u_{2,1}\ v_{2,1}$ $\vdots$ $x_{N,0}\ u_{N,0}\ v_{N,0}\ x_{N,1}\ u_{N,1}\ v_{N,1}$

각 테스트 케이스마다 다음과 같이 출력한다.

$N$개의 공사를 모두 시작했다면 첫째 줄에 YES, 둘째 줄에 길이 $N$인 이진 문자열 $S$를 출력한다. $S_i$는 $i$번째 공사에서 선택한 계획이다.

$k$번째 공사 직전에 중단했다면 첫째 줄에 NO k, 둘째 줄에 이전까지 선택한 계획으로 이루어진 길이 $k-1$의 문자열 $S$를 출력한다. $k=1$이면 둘째 줄에 -를 출력한다.

• $1 \leq T \leq 20$.
• $1 \leq M,N \leq 200\,000$.
• $1 \leq a_e,b_e \leq M$ ($1 \leq e \leq M-1$).
• 주어진 선로들은 모든 역을 연결하는 트리를 이룬다.
• $1 \leq x_{i,b},u_{i,b},v_{i,b} \leq M$ ($1 \leq i \leq N$, $b\in\{0,1\}$).
• 같은 역이나 같은 경로가 여러 번 주어질 수 있다.
• 모든 테스트 케이스에 대한 $M$의 합은 $200\,000$ 이하이다.
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.