관광지 나누기

바쿠에는 $0$번부터 $n-1$번까지 번호가 붙은 $n$개의 관광지와 $0$번부터 $m-1$번까지 번호가 붙은 $m$개의 양방향 도로가 있다. 각 도로는 서로 다른 두 관광지를 잇고, 도로를 따라 임의의 두 관광지 사이를 이동할 수 있다.

파티마는 관광지를 사흘에 걸쳐 모두 방문하려 한다. 첫째 날에는 $a$개, 둘째 날에는 $b$개, 셋째 날에는 $c$개를 방문하기 위해 관광지를 크기가 각각 $a$, $b$, $c$인 세 집합 $A$, $B$, $C$로 나눈다. 각 관광지는 정확히 한 집합에 속하며 $a+b+c=n$이다.

집합 $S$ 안의 임의의 두 관광지 사이를 $S$ 밖의 관광지를 거치지 않고 이동할 수 있으면 $S$를 연결된 집합이라고 한다. 파티마는 $A$, $B$, $C$ 중 적어도 두 집합이 연결되도록 나누고 싶다. 이러한 분할을 올바른 분할이라고 한다.

올바른 분할 하나를 찾거나, 존재하지 않음을 판별하여라.

구현 세부 사항

다음 함수를 구현해야 한다.

vector<int> find_split(int n, int a, int b, int c,
                       vector<int> p, vector<int> q)

• $n$: 관광지의 수
• $a$, $b$, $c$: 집합 $A$, $B$, $C$의 크기
• $p$, $q$: 길이가 $m$인 배열이며 도로 $i$는 $p[i]$와 $q[i]$를 잇는다.
• 길이가 $n$인 배열 $s$를 반환해야 한다.
• 올바른 분할이 없다면 $s$의 모든 원소는 $0$이어야 한다.
• 그렇지 않다면 $s[i]$는 관광지 $i$가 $A$, $B$, $C$ 중 어디에 속하는지에 따라 각각 $1$, $2$, $3$이어야 한다.

예제

예제 1

find_split(9, 4, 2, 3,
           [0, 0, 0, 0, 0, 0, 1, 3, 4, 5],
           [1, 2, 3, 4, 6, 8, 7, 7, 5, 6])

$[1,1,3,1,2,2,3,1,3]$은 가능한 답이다. 이때 $A=\{0,1,3,7\}$, $B=\{4,5\}$, $C=\{2,6,8\}$이며 $A$와 $B$가 연결되어 있다.

예제 2

find_split(6, 2, 2, 2, [0, 0, 0, 0, 0], [1, 2, 3, 4, 5])

올바른 분할이 없으므로 유일한 정답은 $[0,0,0,0,0,0]$이다.

제한

• $3 \leq n \leq 100\,000$
• $2 \leq m \leq 200\,000$
• $1 \leq a,b,c \leq n$
• $a+b+c=n$
• 임의의 두 관광지 사이에는 도로가 최대 하나 있다.
• 모든 관광지는 서로 연결되어 있다.
• 모든 $i$ ($0 \leq i \leq m-1$)에 대해 $0 \leq p[i],q[i] \leq n-1$이고 $p[i] \neq q[i]$이다.

부분 문제

1. (7점) 각 관광지는 최대 두 도로의 끝점이다.
2. (11점) $a=1$
3. (22점) $m=n-1$
4. (24점) $n \leq 2500$, $m \leq 5000$
5. (36점) 추가 제한이 없다.

• 첫째 줄: $n\;m$
• 둘째 줄: $a\;b\;c$
• 이어지는 $m$개 줄의 $i$번째 줄: $p[i]\;q[i]$

• find_split이 반환한 배열을 한 줄에 출력한다.