시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 258 | 114 | 101 | 52.062% |
택희는 이번 대회에 사용하기 위해 그래프를 몇 개 만들었다.
택희의 그래프 데이터는 항상 아래의 형식을 따른다.
N M U1 V1 U2 V2 U3 V3 ... UM VM
위는 정점이 N개, 간선이 M개인 그래프 데이터로, 모든 Ui, Vi에 대해 1 ≤ Ui, Vi ≤ N을 만족하며, N과 M 뒤에 등장하는 간선 정보(U, V 페어)는 정확히 M개이다. 그 외의 다른 조건은 없다.
택희는 대회에 사용할 모든 그래프를 만들었고, 데이터를 업로드하려던 그 순간! 갑자기 영훈이가 나타나 데이터의 여기저기에 임의의 정수를 몇 개 써 넣어 버렸고, 택희는 순간적인 상황 변화를 받아들이지 못하고 격한 욕설을 내뱉으며 영훈이에게 당장 원래 데이터로 고쳐 두라고 말한 뒤 자리를 떠나 버렸다.
영훈이는 최대한 빠르게 그래프 데이터를 복원해야 한다. 하지만 자신이 어디에 어떤 수를 썼는지 전혀 기억하지 못하는 영훈이는 고민에 빠졌다.
영훈이는 자신이 데이터에 한 일은 수를 임의의 위치에 넣은 것뿐이라는 것을 알기에, 데이터에서 몇 개의 수를 지워 그래프 데이터를 만들려 한다. 즉, 수들의 원래 순서를 유지하면서 수 일부를 지워, 남은 수들이 '올바른 데이터' 가 되도록 하려는 것이다. 이때 '올바른 데이터' 란,
영훈이는 그래프를 복원할 방법이 여러 가지라면 기왕이면 노드의 수(N)가 가장 큰 것을, 그러한 것도 여러 가지라면 간선의 수(M)가 가장 큰 것을 복원할 것이다.
현재 데이터의 상태가 주어졌을 때, 영훈이가 복원할 그래프의 노드의 수와 간선의 수를 알아내보도록 하자.
첫째 줄에 데이터에 기록되어 있는 정수의 개수 K가 주어진다. (4 ≤ K ≤ 200,000)
이어 둘째 줄에 데이터에 기록된 수 a1, a2, ..., ak가 순서대로 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 200,000)
영훈이가 복원할 그래프의 노드의 수 N과 간선의 수 M을 공백으로 구분하여 출력한다.
그러한 것이 여러 가지라면 N이 가장 큰 것을, 그런 것도 여러 가지라면 M이 가장 큰 것을 골라야 한다.
만약 수를 어떻게 지우더라도 올바른 데이터를 만들 수 없다면 첫째 줄에 -1 하나만을 출력한다.
4 2 1 1 1
2 1
영훈이가 아무 수도 지우지 않으면 아래와 같은 그래프를 만들 수 있다.
12 5 5 2 9 8 2 6 12 8 1 5 14
9 2
5 5 2 9 8 2 6 12 8 1 5 14
위와 같이 정점이 9개, 간선이 2개인 그래프를 만들 수 있다.
4 1 2 3 4
-1
University > 연세대학교 > 2019 연세대학교 컴퓨터과학과 프로그래밍 경진대회 E번