"Astra"는 플레이어들이 번갈아 가며 별에 표시를 하여 별자리를 발견하는 아름다운 보드게임입니다. 이 게임은 전술과 전략이 교묘하게 어우러져 있으며, 간결하고 직관적인 규칙 덕분에 배우기 쉽고 빠르게 즐길 수 있습니다.

Photo by @kavics004 on BoardGameGeek

Alice와 Bob이 하는 2인용 게임을 생각해 봅시다. 이 게임에는 트리 모양의 별자리가 있으며, 이는 $n$개의 별($1$부터 $n$까지 번호가 매겨짐)과 $(n - 1)$개의 간선으로 이루어진 연결 그래프로 볼 수 있습니다. 처음에는 단 하나의 별 $s$에만 표시가 되어 있습니다. Alice와 Bob은 다음 규칙에 따라 번갈아 가며 남은 별들에 표시를 합니다:

• 매 턴마다 플레이어는 최소 $1$개 이상, 최대 $k$개 이하의 별에 표시를 해야 합니다.
• 각 별은 단 한 번만 표시할 수 있습니다.
• 한 턴에 표시된 별들을 표시된 순서대로 $a_1, a_2, \cdots, a_p$라고 합시다:
  • $a_1$에 표시할 때, 이 별은 이미 표시된 별의 이웃이어야 합니다.
  • 모든 $2 \le i \le p$에 대해, $a_i$에 표시할 때, 이 별은 $a_{i-1}$의 이웃이어야 합니다.

두 별 $u$와 $v$가 간선으로 직접 연결되어 있으면 두 별은 이웃이라고 합니다.

마지막 별에 표시를 하는 플레이어가 별자리를 차지합니다. Alice가 먼저 시작하고 두 플레이어 모두 최선의 전략으로 플레이한다고 할 때, 각 $1 \le s \le n$에 대해 누가 별자리를 차지할지 결정하세요.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 100$)가 주어집니다. 각 테스트 케이스에 대해:

첫 번째 줄에는 별의 개수와 매 턴마다 표시할 수 있는 별의 최대 개수를 나타내는 두 정수 $n$과 $k$ ($2 \le n \le 2 \times 10^3$, $1 \le k < n$)가 주어집니다.

다음 $(n - 1)$개의 줄 중 $i$번째 줄에는 별 $u_i$와 $v_i$를 연결하는 간선이 있음을 나타내는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n$)가 주어집니다.

모든 테스트 케이스에서 $n$의 합은 $2 \times 10^3$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스마다 문자열 $d_1 d_2 \cdots d_n$ ($d_i \in \{0, 1\}$)을 포함하는 한 줄을 출력합니다. 여기서 $d_i$는 $s = i$일 때 누가 별자리를 차지하는지를 나타냅니다. Alice가 이기면 $d_i = 1$이고, 그렇지 않고 Bob이 이기면 $d_i = 0$입니다.

예제

입력 1

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

출력 1

011000
000
101

노트

첫 번째 예제 테스트 케이스가 위 그림에 나타나 있습니다.

• $s = 1$인 경우를 생각해 봅시다. 첫 번째 턴에서 Alice는 $\{2\}$, $\{2, 3\}$, 또는 $\{2, 6\}$에 표시하는 세 가지 선택지가 있습니다. 만약 Alice가 $\{2, 6\}$을 선택하면, Bob은 그다음에 $\{3\}$에 표시할 수 있으며, 서로 떨어진 $2$개의 별이 남게 됩니다. 이후 턴에서는 각 플레이어가 별을 하나씩만 표시할 수 있으므로 Bob이 승자가 됩니다. Alice의 다른 선택지들도 비슷하게 분석할 수 있습니다.
• $s = 2$인 경우를 생각해 봅시다. 첫 번째 턴에서 Alice는 $\{1\}$, $\{3\}$, $\{6\}$, $\{3, 4\}$, 또는 $\{3, 5\}$에 표시하는 다섯 가지 선택지가 있습니다. Alice는 $\{3\}$에 표시하는 것을 선택할 수 있으며, 서로 떨어진 $4$개의 별이 남게 됩니다. 이후 턴에서는 각 플레이어가 별을 하나씩만 표시할 수 있으므로 Alice가 승자가 됩니다.

두 번째 예제 테스트 케이스에서는 $k = 1$이므로 정확히 $3 - 1 = 2$번의 턴이 진행되며, 따라서 항상 Bob이 승자가 됩니다.

세 번째 예제 테스트 케이스에서는 $s = 1$ 또는 $s = 3$이면 Alice가 남은 $2$개의 별에 바로 표시하고 별자리를 차지할 수 있습니다.