Teoretičar

꼬마 앨런이 심심해하자 고란은 재미있는 문제를 내 주기로 했다. 앨런은 시험 준비로 바빴고, 고란은 옛날 프로그래밍 대회 시절에 풀었던 거대한 이분 그래프 하나만 떠올릴 수 있었다. 고란은 그 그래프를 앨런에게 주며 말했다. 이 이분 그래프의 간선을 같은 색을 가진 두 간선이 정점을 공유하지 않도록, 가능한 한 적은 색으로 칠해야 한다.

앨런은 방으로 달려가 이동식 읽기/쓰기 장치를 꺼내 테이프를 준비하고 문제를 풀기 시작했다. 그러나 곧 무언가 빠졌다는 것을 깨닫고 고란에게 돌아가 말했다. 무한한 테이프를 주면 제가 문제를 풀어 보이겠어요! 고란은 앨런을 날카롭게 쳐다보며 말했다. 무한한 테이프라고? 모든 것을 이론으로만 따지고 들면, 네 이름이 붙은 것은 하나도 남지 않을 거다.

앨런이 울상이 되는 것을 보고 고란은 봐주기로 했다. 조건을 조금 쉽게 해 주마. $C$를 설명한 방식대로 그래프를 칠하는 데 필요한 최소 색의 수라고 하자. $X$는 $C$ 이상인 2의 거듭제곱 중 가장 작은 수이며, 최대 $X$개의 색을 사용해도 된다. 앨런을 도와 문제를 풀어라.

첫째 줄에 양의 정수 $L$, $R$, $M$이 주어진다 ($1 \le L, R \le 100000$, $1 \le M \le 500000$). 각각 이분 그래프의 한쪽 정점 수, 다른 쪽 정점 수, 간선 수이다. 이어서 $M$개의 줄에 양의 정수 $a_i$ ($1 \le a_i \le L$)와 $b_i$ ($1 \le b_i \le R$)가 주어진다. 이는 첫 번째 쪽의 $a_i$번 정점과 두 번째 쪽의 $b_i$번 정점을 잇는 간선이다. 모든 $(a_i, b_i)$ 쌍은 서로 다르다.

첫째 줄에 사용한 색의 수 $K$를 양의 정수 하나로 출력한다. 이어서 $M$개의 줄에 $i$번째 간선의 색 $c_i$ ($1 \le c_i \le K$)를 양의 정수 하나로 출력한다.