실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
휴가 동안, 개발자 주환은 JTube라는 새로운 동영상 공유 서비스를 만들었습니다. JTube에서 친구들은 재미있는 동영상을 녹화하고, 서로 공유하며, 발견할 수 있습니다. 이미 친구들은 개의 동영상 ()을 게시했고, 이를 편리하게 으로 번호가 매겨졌습니다. 그러나 주환은 친구들이 좋아할 만한 새로운 동영상을 어떻게 찾아주어야 할 지 알아내지 못하고 있습니다.
주환은 모든 JTube 동영상에 대해 '추천 동영상' 목록을 만들고 싶어합니다. 이렇게 하면 친구에게 이미 보고 있던 동영상과 가장 관련이 있는 동영상들을 추천할 수 있게 됩니다.
주환은 '관련성'이라는 척도를 고안하였는데, 이는 두 동영상이 서로 얼마나 관련성이 있는 지를 판단합니다. 그는 개의 동영상 쌍을 선택하고 그들 사이의 관련성을 수동으로 계산합니다. 그 다음, 주환은 각 동영상이 노드이고 그가 수동으로 고려하였던 개의 동영상 쌍이 연결되어 있는 네트워크로 동영상을 시각화합니다. 편리하게도, 주환은 임의의 동영상이 정확히 하나의 연결 경로를 따라 다른 동영상에 도달할 수 있도록 개의 쌍을 선택했습니다. 주환은 두 동영상 간의 관련성은 이 경로상의 모든 연결의 최소 관련성으로 정의되어야 한다고 결정합니다.
주환은 주어진 JTube 동영상 옆에, 그 비디오와의 관련성이 이상인 모든 다른 동영상들이 추천되도록 값을 설정하려고 합니다. 그러나, 주환은 너무 많은 동영상들이 친구들에게 추천될 수 있을 것을 걱정하고 있는데, 이는 그들의 시험 공부를 방해할 수 있습니다! 따라서 그는 신중하게 값의 적합한 수준을 설정하려고 합니다. 주환은 값에 따른 추천 동영상에 대한 여러 가지 질문에 대한 답변하는 것을 당신이 도와주는 것을 원합니다.
첫 번째 입력 줄에는 과 ()가 포함됩니다.
다음 개의 줄은 주환이 수동으로 비교한 동영상 쌍을 각각 설명합니다. 각 줄에는 세 개의 정수 , , 그리고 ()가 포함되어 있으며, 이는 와 동영상이 의 관련성으로 연결되어 있음을 나타냅니다.
다음 개의 줄은 주환의 개의 질문을 설명합니다. 각 줄에는 두 개의 정수, 와 ()가 포함되어 있으며, 이는 FJ의 번째 질문이 일 때 비디오 를 보는 사람들에게 몇 개의 동영상이 추천될 것인지 묻는다는 것을 의미합니다.
개의 줄을 출력합니다. 번째 줄에는 FJ의 번째 질문에 대한 답변을 출력합니다.
4 3 1 2 3 2 3 2 2 4 4 1 2 4 1 3 1
3 0 2
주환은 동영상 1과 2가 관련성이 3인 것을, 동영상 2와 3이 관련성이 2인 것을, 그리고 동영상 2와 4가 관련성이 4인 것을 발견합니다. 이를 기반으로, 동영상 1과 3의 관련성은 min(3, 2) = 2이며, 동영상 1과 4의 관련성은 min(3, 4) = 3이며, 그리고 동영상 3과 4의 관련성은 min(2, 4) = 2입니다.
주환은 일 때 동영상 2에서 몇 개의 동영상이 추천될지, 일 때 동영상 1에서 몇 개의 동영상이 추천될지, 그리고 일 때 동영상 1에서 몇 개의 동영상이 추천될지 알고 싶어합니다. 우리는 일 때, 동영상 1, 3, 그리고 4가 동영상 2에서 추천되는 것을 볼 수 있습니다. 일 때는 동영상 1에서 어떤 동영상도 추천되지 않을 것입니다. 그러나 일 때는 동영상 2와 4가 동영상 1에서 추천될 것입니다.