경주 지도 라벨 붙이기

모터사이클 경주 조직위원회가 대회 지도에 라벨을 붙이려 한다. 지도에는 장소 $n$개가 있고, 각 장소에는 $0$번부터 $n-1$번까지 번호가 붙어 있다. 모든 도로는 양방향이고 서로 다른 두 장소를 잇는다.

각 장소에는 일반을 뜻하는 $0$이나 지원을 뜻하는 $1$을 라벨로 붙인다. 장소 $i$에 닿아 있는 도로가 $d_i$개일 때, 장소 $i$와 라벨이 같은 이웃은 최대 $\lfloor d_i / 2 \rfloor$개까지만 허용한다. 이 조건을 지키는 라벨링은 보통 여러 가지이므로, 다음 절차가 만들어내는 라벨링 하나만 정답으로 인정한다.

1. 모든 장소의 라벨을 $0$으로 둔다.
2. 조건을 어기는 장소가 있으면 그중 번호가 가장 작은 장소를 골라 라벨을 뒤집는다. 즉 $0$이면 $1$로, $1$이면 $0$으로 바꾼다.
3. 조건을 어기는 장소가 하나도 남지 않을 때까지 2를 반복한다.

라벨을 한 번 뒤집을 때마다 양 끝의 라벨이 서로 다른 도로의 수가 최소 $1$ 늘어나므로, 이 절차는 항상 유한 번 만에 끝난다.

첫 줄에 장소의 수 $n$이 주어진다. ($1 \le n \le 1000$)

다음 $n$개 줄 가운데 $i$번째 줄은 장소 $i$를 설명한다. ($i = 0, 1, \dots, n-1$) 각 줄의 형식은 다음과 같다.

number_of_neighbors: neighbor1 neighbor2 ... neighborm

number_of_neighbors는 장소 $i$에 닿아 있는 도로의 수이고, 그 뒤에 이웃 장소의 번호가 공백으로 구분되어 나열된다. 2: 1 2는 이웃이 둘이고 그 번호가 $1$과 $2$라는 뜻이다.

한 도로가 같은 장소를 두 번 잇는 경우는 없고, 같은 두 장소를 잇는 도로도 하나뿐이다. 장소 $a$의 이웃 목록에 $b$가 있으면 장소 $b$의 이웃 목록에도 $a$가 있다. 이웃이 없는 장소의 줄은 콜론에서 끝난다.

첫 줄에 $n$을 출력한다. 이어서 $n$개 줄에 장소 $0$번부터 차례로 라벨을 붙여 출력한다. 각 줄의 형식은 다음과 같다.

label number_of_neighbors: neighbor1 neighbor2 ... neighborm

label은 일반이면 $0$, 지원이면 $1$이다. 이웃 목록은 입력에 주어진 순서 그대로 출력한다. 토큰 사이는 공백 하나로 구분하고, 콜론은 number_of_neighbors 바로 뒤에 붙여 쓴다. 이웃이 없는 장소의 줄은 콜론에서 끝난다.