문제
아기 재민이는 작은 장난감 그래프를 선물받았다.
이 그래프는 이분 그래프의 모양을 하고 있어 왼쪽에 L개, 오른쪽에 R개의 정점이 있다.
재민이는 선물받은 그래프가 너무 밋밋해서 마음에 들지 않았다.
그래서 그래프의 간선들을 색칠해주기로 했다!
재민이는 여러가지 색의 물감을 간선에 발라 색칠한다.
밋밋한 걸 싫어하는 재민이는 한 끝점을 공유하는 두 간선이 같은 색으로 색칠되는 일이 없게 하려고 한다.
재민이는 물감을 많이 꺼내기 귀찮기 때문에 가능한 한 물감을 적게 쓰려고 한다.
그런데 재민이에게 한 가지 문제가 생겼다!
재민이가 도저히 그런 색칠 방법을 아무리 생각하려 해봐도 찾을 수가 없었던 것이다!
재민이는 고심 끝에 최소의 색깔을 쓰는 것을 포기했다.
그래프를 색칠할 수 있는 최소의 색깔 수가 C라고 하자.
재민이는 최소의 색깔 수 대신에 2^k >= C 인 최소의 2^k보다 작거나 같은 개수의 색을 사용하기로 했다.
하지만 이렇게 조건을 바꾸어도 재민이는 여전히 색칠 방법을 찾지 못했다.
여러분이 재민이가 원하는 대로 그래프를 색칠하는 방법을 대신 알려주자!
입력
첫 줄에 L, R과 간선의 개수 M이 주어진다.
이후 M줄에 걸쳐 간선의 정보가 줄마다 u v 꼴로 주어진다.
이는 왼쪽 집합의 u번 정점과 오른쪽 집합의 v번 정점을 잇는 간선이 존재한다는 의미이다.
<제한>
- 1 <= L <= 100000
- 1 <= R <= 100000
- 1 <= M <= 500000
- 그래프에 중복 간선은 주어지지 않는다.
<서브태스크>
#1 (20점) : L <= 100, R <= 100
#2 (30점) : L <= 5000, R <= 5000
#3 (50점) : 추가적인 제한 조건이 없다.
출력
첫 줄에 사용한 색깔의 종류 K를 출력하라.
이후 M줄에 걸쳐 입력으로 주어진 순서에 맞춰 각 간선에 칠해야 할 색깔의 번호를 출력하라.
색깔의 번호는 1~K사이의 정수여야 하며 색칠의 결과는 문제의 조건을 만족해야 한다.
예제 #1
3 3 5
1 1
1 2
2 2
2 3
3 3
2
1
2
1
2
1
예제 #2
2 4 4
1 1
1 2
1 3
2 4
4
1
2
3
4
로그인해야 코드를 작성할 수 있어요.