벨트 컨베이어

JOI 주식회사의 공장에는 0번부터 $N - 1$번까지 번호가 붙은 테이블이 $N$개 있습니다. 또 0번부터 $N - 2$번까지 번호가 붙은 벨트 컨베이어가 $N - 1$개 있습니다. 벨트 컨베이어 $i$ ($0 ≤ i ≤ N - 2$)는 테이블 $A_i$와 테이블 $B_i$를 잇고, 한쪽 테이블에서 다른 쪽 테이블로 제품을 운반합니다. 운반 방향은 겉으로 보이지 않습니다. 방향을 무시하면 모든 테이블 쌍이 컨베이어를 거쳐 서로 연결되어 있습니다.

IOI 군은 공장장입니다. 그는 각 컨베이어의 운반 방향을 잊어버려서 다음 작업을 여러 번 반복합니다.

1. 컨베이어를 여러 개 고르고, 고른 컨베이어의 운반 방향을 뒤집습니다.
2. 테이블을 여러 개 고르고, 고른 테이블마다 제품을 한 개씩 올립니다.
3. 제품이 올라간 테이블마다 다음 중 하나가 동시에 일어납니다.
   1. 그 테이블에서 제품을 내보내는 컨베이어가 없으면 아무 일도 일어나지 않습니다.
   2. 그 테이블에서 제품을 내보내는 컨베이어가 하나 이상 있으면, 제품은 그중 하나를 타고 이동합니다. 제품은 그 컨베이어의 도착 테이블에 멈추고 더 이상 움직이지 않습니다.
4. IOI 군은 각 테이블에 제품이 있는지 확인합니다. 제품이 있으면 모두 가져갑니다.
5. 1번 작업에서 방향을 뒤집은 컨베이어마다 IOI 군이 방향을 원래대로 되돌립니다.

IOI 군은 이 작업을 최대 30번 수행하여 모든 컨베이어의 원래 방향을 알아내려고 합니다.

모든 입력은 다음 조건을 만족합니다.

• $0 ≤ A_i ≤ N - 1$ ($0 ≤ i ≤ N - 2$).
• $0 ≤ B_i ≤ N - 1$ ($0 ≤ i ≤ N - 2$).
• 방향을 무시하면 모든 테이블 쌍이 벨트 컨베이어를 거쳐 연결되어 있습니다.