30196번 - 트리 만들기 스페셜 저지

문제

거리가 3ドル$만큼 떨어진 순서 없는 정점 쌍을 정확히 $K$개 찾을 수 있는, 정점의 개수가 $N$개인 트리를 구성할 수 있는지 판별하라. 만약 구성할 수 있다면, 조건을 만족하는 트리를 아무거나 하나 출력하라.

여기서 두 정점 사이의 거리란, 한 정점과 다른 정점을 잇는 유일한 단순 경로 위의 간선의 개수로 정의된다.

입력

첫 번째 줄에 트리의 정점 개수 $N$과 문제의 정수 $K$가 공백으로 구분되어 주어진다. (2ドル\le N\le 500,円 000,ドル 0ドル\le K\le\frac{N(N-1)}{2}$)

출력

첫 번째 줄에 조건을 만족하는 트리를 구성할 수 있는지 여부를 출력한다. 구성할 수 있다면 YES를, 없다면 NO를 출력한다. 답이 YES인 경우, 두 번째 줄부터 $N-1$개의 줄에 간선의 양 끝 정점의 번호를 공백으로 구분해서 출력한다. 정점의 번호는 1ドル$ 이상 $N$ 이하의 정수여야 한다.

제한

힌트

입력으로 주어지는 $K$의 값이 32비트 정수 변수가 표현할 수 있는 범위를 넘을 수 있다. 64비트 정수 변수(C++의 경우 long long type)를 사용할 것을 권장한다. 또한 트리란 $N$개의 정점과 $N-1$개의 간선을 가지는 무방향 연결 그래프이다.