23086번 - 두 반으로 나누기

종민이는 CTP 초등학교 5학년 3반 담임 교사로 일하고 있다. 최근 들어 CTP 초등학교에 전학을 오는 5학년 학생들이 많아져서, 대책으로 종민이가 담당하는 3반을 2개 분반으로 나누기로 했다.

종민이는 이전부터 자신이 담당하는 반의 학생들로부터 고통을 받고 있었다. 5학년 3반 친구들은 수업 시간임에도 불구하고 친구들끼리 놀면서 수업을 듣기를 거부하는 일이 많기 때문에, 5학년 3반의 분반은 종민이에게 매우 희소식이었다.

종민이는 5학년 3반의 모든 친한 친구인 두 학생을 서로 다른 분반에 배치하여 고통을 줄이려고 한다. 하지만 그런 배치가 불가능한 경우도 있기 때문에, 이를 위해 한가지 묘책을 생각해 냈다. 그것은 바로 친한 친구 관계인 두 학생이 서로 험담을 한다는 소문을 퍼뜨려 두 친구를 절교시키는 것이다! 친한 친구인 두 학생이 절교하면 더 이상 친한 친구가 아니게 된다.

종민이는 이런 식으로 절교시킬 친한 친구 쌍의 리스트를 만들었다. 물론 친한 친구 쌍들을 마구 절교시키다가 학생들끼리 파벌이 나뉘어 싸움이 나는 것은 원하지 않기 때문에, 해당 리스트의 모든 친한 친구 쌍을 절교시켜도 학생들끼리 파벌이 나뉘지는 않도록 했다. 파벌이 나뉘지 않는다는 말은, 친한 친구 관계인 두 학생을 모두 간선으로 이은 그래프가 연결 그래프임을 뜻한다.

종민이는 리스트에 쓰인 차례대로 친한 친구인 두 학생을 절교시킨 다음, 두 분반에 모두 친한 친구인 두 학생이 없도록 학생들을 배치하여 평화를 찾으려고 한다. 하지만 선생으로서 마지막 양심이 남아있었던 종민이는, 친한 친구 쌍을 절교시키는 일을 최소한으로 하려고 한다. 최소 몇 쌍의 친한 친구를 절교 시켜야 각 분반에 친한 친구인 두 학생이 없도록 학생들을 나눌 수 있을까?

첫째 줄에 \(N\), \(M\), \(K\)가 공백으로 구분되어 주어진다.

• \(N\)은 5학년 3반의 학생 수이다.
• \(M\)은 5학년 3반의 친한 친구 쌍의 수이다.
• \(K\)는 종민이가 절교시킬 리스트에 포함되어 있는 친한 친구 쌍의 개수이다.

둘째 줄부터 \(M\)개의 줄에 걸쳐, \(i\)번째 친한 친구 쌍을 나타내는 \(u_i\), \(v_i\)가 공백으로 구분되어 주어진다. 이는 \(u_i\)번 학생과 \(v_i\)번 학생이 친한 친구임을 뜻한다. 중복된 관계는 주어지지 않는다.

\(M\)+2번째 줄부터 \(K\)개의 줄에 걸쳐 \(R_i\)가 주어진다. 이는 \(i\)번째로 절교시킬 친한 친구 쌍이 \(R_i\)번째 친한 친구 쌍임을 뜻한다. 입력되는 \(R_i\)는 모두 서로 다름이 보장된다.

첫째 줄에 절교시켜야하는 최소 친한 친구 쌍의 개수를 출력한다.

둘째 줄에 두 분반의 각 학생 수를 오름차순으로 출력한다.

만약 리스트의 모든 친한 친구 쌍을 절교시켜도 두 분반으로 나눌 수 없다면, 대신 첫째 줄에 "-1"을 출력한다.

• 2 ≤ \(N\) ≤ 10⁵
• \(N\) - 1 ≤ \(M\) ≤ min(\(\frac{N(N - 1)}{2}\), 2 × 10⁵)
• 0 ≤ \(K\) ≤ \(M\) - \(N\) + 1
• 1 ≤ \(u\), \(v\) ≤ \(N\), \(u \ne v\)
• 1 ≤ \(R_i\) ≤ \(M\) 

1번 예제의 초기 친한 친구 관계를 그래프로 나타내면 다음과 같다.

종민이는 5번째, 3번째, 그리고 7번째 친한 친구 쌍을 차례대로 절교시키려고 한다. 이 중 5번째와 3번째, 두 쌍을 절교시키면 한 분반에는 1, 4번 학생을, 나머지 분반에는 2, 3, 5번 학생을 배치함으로써 각 분반에 친한 친구 쌍이 없도록 나눌 수 있다.

이보다 적은 쌍을 절교시키면서 문제의 조건을 만족하도록 하는 것은 불가능하다.