3485 - K - K-Graphs

Created by Luis Manuel Díaz Barón
Added by luismo (2015-12-07)
Limits
Total Time: 30000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Given two integer numbers N and K, can you determine if it is possible to build a graph of N vertices such that exactly K of them have degree equal to K?

Degree of a vertex is defined as the number of edges that are connected to the vertex.

Take into account that no self-loops or multiple (parallel) edges are allowed.
Dados dos enteros N y K (1 K N 103), ¿puedes determinar si es posible construir un grafo de N nodos de modo que exactamente K nodos tienen grado igual a K?

El grado de un vértice se define como el número de aristas que están conectadas con ese nodo.

Tenga en cuenta que no se permiten lazos ni aristas múltiples (paralelas).
Given two integer numbers N and K, can you determine if it is possible to build a graph of N vertices such that exactly K of them have degree equal to K?

Degree of a vertex is defined as the number of edges that are connected to the vertex.

Take into account that no self-loops or multiple (parallel) edges are allowed.

Input specification

A single line containing two space-separated integers: N and K (1 K N 103).
Una sola línea que contiene dos enteros separados por un espacio: N y K (1 K N 103).
A single line containing two space-separated integers: N and K (1 K N 103).

Output specification

If the graph can be built, print a line containing the word "YES", without quotes, otherwise print the word "NO".

If the answer is "YES", then you must output an instance of such a graph. Output a single integer E in the next line, representing the number of edges in the graph. Then, list the edges of the graph in the next E lines. For each edge, you must print two space-separated integers A and B (1 A, B N), describing an edge between node A and node B. If several solutions exist, print any of them.
Si es posible construir el grafo, imprima una línea con la palabra "YES", sin las comillas, en caso contrario imprima la palabra "NO".

Si la respuesta es "YES", entonces debe imprimir un ejemplo de ese grafo. Imprima un entero E en la línea siguiente, representando el número de aristas del grafo. Luego, imprima la lista de aristas del grafo en las siguientes E líneas. Para cada arista, se debe imprimir dos enteros A y B (1 A, B N) separados por un espacio, describiendo una arista entre el nodo A y el nodo B. En caso de existir varias soluciones, imprima una de ellas.
A single line containing two space-separated integers: N and K (1 K N 103).

Sample input

8 3

Sample output

YES
6
1 2
1 3
2 3
1 4
2 5
3 5

Hint(s)

http://coj.uci.cu/contest/
http://coj.uci.cu/contest/
http://coj.uci.cu/contest/