프로그램 명: ruins
제한시간: 1 초
모험가 심영은 탐험을 하던 중 동굴 형태의 고대 유적을 발견했다. 유적 입구의 문은 굳게 닫혀 있었고, 입구 옆쪽에 있는 평평한 바위 위에는 숫자가 쓰여진 알약 2개가 올려져 있었다. 문을 힘으로 열어보려고 하다가 지친 심영에게 고대 문자로 쓰여진 벽면의 글귀가 눈에 띄었다. 이 문자들을 해독한 결과, 심영은 다음과 같은 사실들을 알 수 있었다.
-
유적 안의 길은 갈림길이 없는 일직선 형태이며, 유적 안 곳곳에는 값어치가 엄청난 고대 유물들이 흩어져 있다.
-
유적에는 입구의 문을 포함하여 가로막힌 문이 총 M개 있으며, 각각의 문 앞에는 1 ~ N-1 중 하나의 숫자가 쓰여진 알약이 2개씩 놓여 있다.
-
문에는 고대의 마법이 걸려 있어서 문 앞에 놓인 두 개의 알약 중 하나를 먹게 되면 문이 열린다. 다른 방법으로는 문을 열 수 없다.
-
두 숫자의 합이 N이 되는 두 알약을 먹게 되면 저주가 발동되어 죽는다. 즉 이전에 숫자 i가 쓰여진 알약을 먹은적이 있었다면, N-i가 쓰여진 알약을 먹으면 죽게 된다.
-
똑같은 숫자가 쓰여진 알약이 여러 개 존재할 수 있다. 심지어 어떤 문 앞에 놓인 두 개의 알약의 숫자가 같을 수도 있다. 하지만 1 <= i <= N-1 인 모든 i에 대해, 숫자 i가 쓰여진 알약의 총 개수는 많아봐야 [sqrt(N)]+1개를 넘지 않음을 만족한다.
다행스럽게도, 벽면의 글귀 아래에는 유적 내부의 지도가 그려져 있었고 지도에는 가로막힌 문과 그 앞에 놓여있는 알약의 숫자까지 표시되어 있었다.
다른 모험가들 여러 명과 같이 온다면 아무도 죽지 않고 유적 내부를 모두 탐사할 수 있겠지만, 돈에 욕심이 난 심영은 일단 혼자서 유적을 가능한 한 깊은 곳까지 탐색하고 그 과정에서 얻은 유물들을 혼자 차지하려 한다. 과연 심영은 죽지 않고 유적 안을 얼마나 깊은 곳까지 탐험할 수 있을까?
입력
-
첫 줄에 N과 M이 주어진다(5 <= N <= 3000, 1 <= M <= 10000).
-
다음 M줄에는 각각의 닫힌 문 앞에 놓여진 알약에 대한 정보가 주어진다. i+1번째 줄에 들어오는 두개의 값은 i번째 문 앞에 놓여진 두 알약의 번호이다.
출력
심영이가 죽지 않고 통과할 수 있는 문의 최대 개수를 출력한다.
입출력 예
입력
7 6
1 2
1 4
2 3
3 6
4 5
4 6
출력
6
입력
12 11
1 4
2 3
4 11
6 8
5 9
3 5
8 10
6 7
1 2
3 11
2 9
출력
7
입력
10 2
5 5
5 5
출력
1
입출력 보충
- 첫번째 예제 : 순서대로 2, 4, 2, 6, 4, 4를 먹으면 6번째 문까지 통과할 수 있다.
- 두번째 예제 : 순서대로 4, 3, 4, 6, 5, 5, 10을 먹으면 7번째 문까지 통과할 수 있다.
- 세번째 예제 : 2번째 문까지 통과하려면 5를 두 번 먹어야 하며, 그러면 5+5=10이 되어 죽게 된다. 따라서 답은 1이다.
출처: jhp109
[질/답]
[제출 현황]
[푼 후(0)]