예비 정비팀

철도망에는 $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})$에도 대기 중인 팀이 남아 있다.

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

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

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

$T$ case$_1$ case$_2$ $$

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

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

• $1 \leq T \leq 20$.
• $1 \leq M,N \leq 200\,000$.
• $$ ().