국회 정당 나누기

멀리 떨어진 어느 나라의 국회에는 의원이 $N$명 있다. 이번 주 월요일부터 금요일까지 의원 전원이 매일 출근해 새 국민투표 법률의 개정안을 두고 하루 종일 언쟁했다.

한 기자가 닷새 동안 매일 한 장씩, 언쟁이 한창일 때의 의사당을 사진으로 찍었다. 사진 한 장에는 서로 얼굴을 맞대고 다투는 의원 쌍이 담겨 있다. 사진 다섯 장을 모두 분석한다.

의원은 모두 두 정당 중 한 곳에 속한다. 두 정당을 A와 B로 적는다. 각 의원이 자기 정당 의원 중 다툰 상대가 두 명을 넘지 않도록 소속을 정한다.

같은 쌍이 여러 날 사진에 나올 수 있다. 이때도 두 의원에게 다툰 상대는 한 명으로 센다.

첫 줄에 의원 수 $N$이 주어진다 ($2 \le N \le 200000$). 의원에게는 1번부터 $N$번까지 번호가 붙어 있다.

이어지는 다섯 줄은 월요일부터 금요일까지 찍은 사진을 순서대로 설명한다. 각 줄에는 그날 사진에 담긴, 다투고 있는 의원 쌍의 목록이 있다. 먼저 쌍의 수 $P$가 주어지고 ($1 \le P \le N/2$), 이어서 $P$개의 쌍이 "$K$ $L$" 꼴로 나온다. $K$와 $L$은 서로 다투는 두 의원의 번호다. 각 쌍 앞에는 공백이 두 개 있다. 한 의원은 한 줄에 최대 한 번 나온다.

A와 B로만 이루어진 길이 $N$의 문자열을 한 줄에 출력한다. $K$번째 문자는 $K$번 의원의 정당이다.

조건을 만족하는 배정은 여러 가지가 있으므로, 다음 절차로 얻는 배정만 정답으로 인정한다.

1. 의원 전원을 정당 A에 넣는다.
2. 자기 정당 의원 중 다툰 상대가 세 명 이상인 의원이 있으면, 그런 의원 가운데 번호가 가장 작은 의원 한 명을 반대 정당으로 옮긴다.
3. 그런 의원이 없어질 때까지 2번을 반복한다.

한 의원은 사진 한 장에 최대 한 번 나오므로 다툰 상대가 최대 다섯 명이다. 따라서 옮긴 의원은 옮긴 직후 자기 정당의 다툰 상대가 두 명 이하가 되고, 같은 정당끼리 다툰 쌍의 수는 옮길 때마다 줄어든다. 그래서 절차는 반드시 끝난다.