After having read all the books and watched all the movies from the ‘Jurassic Park’ franchise, Jarvi now knows all about dinosaurs. He has decided to build his own ‘Jurassic Park’ …no, parks are too small, Jarvi will build his own ‘Jurassic Jungle’.
Jarvi has already started breeding $N$ different dinosaurs. His Jurassic Jungle will have exactly $N$ dinosaur-homes (called dinohomes), numbered from $1$ to $N$, each with exactly one dinosaur.
Jarvi knows the secret of keeping dinosaurs happy: every day, each dinosaur must be able to walk around Jurassic Jungle, visiting all other dinohomes, and safely return to his own dinohome before midnight.
To achieve this, Jarvi will build $M$ bidirectional roads, each connecting $2$ different dinohomes. Jarvi does not want to build more than one road between any pair of dinohomes.
However, this is not an easy task, as dinosaurs are not good with directions. Starting from his dinohome, a dinosaur will randomly select any dinohome that he has not visited before, and walk there.
The dinosaur will be happy iff no matter how he randomly chooses the path, he must be able to visit all other $N - 1$ other dinohomes, and from the last dinohome he visits he must be able to walk directly to his own dinohome.
Consider the following Jurassic Jungle with $N = 4$ and $M = 5$:
Consider the dinosaur in dinohome numbered $1$:
At the start of his walk, he has only visited dinohome numbered $1$ — his own dinohome. Thus he can randomly choose to walk to one of dinohomes $2$, $3$ or $4$.
If the dinosaur chooses to walk to dinohome $2$:
He can only continue to walk to dinohome $3$, as dinohome $1$ was already visited.
From dinohome $3$, he can only walk to dinohome $4$, since dinohomes $1$ and $2$ were already visited.
From dinohome $4$, he can directly walk to his own dinohome.
If the dinosaur chooses to walk to dinohome $3$:
He can randomly choose to walk to either dinohome $2$ or $4$.
If he chooses to walk to dinohome $2$, he cannot continue his walk, as both dinohomes $1$ and $3$ were visited.
Thus the dinosaur at dinohome $1$ will NOT be happy, since he might not be able to visit all other $N - 1$ dinohomes, depending on how he chooses the path.
Let’s also consider the dinosaur in dinohome numbered $2$. Starting at his home, he can walk to dinohomes $1$, $3$ and $4$ in this order. At dinohome $4$, this dinosaur has visited all other $3$ dinohomes, but he cannot directly walk back to his dinohome. Thus the dinosaur at dinohome $2$ will NOT be happy.
Please help Jarvi build his Jurassic Jungle so that all his $N$ dinosaurs are happy.
The input contains at most $30$ test cases. Each test case contains a single line with exactly $2$ space-separated integers $N$ and $M$. $(3 \le N \le 30, 0 \le M \le N (N - 1) / 2)$. The last line of the input contains two $-1$s and does not represent a test case.
For each test case, if it is impossible to build a Jurassic Jungle satisfying the given conditions, print a single line containing ‘NO’.
Otherwise, print a line containing ‘YES’, followed by $M$ lines. Each line should contain $2$ integers $u$ and $v$, representing a road between the $u$-th dinohome and the $v$-th dinohome. Every road should connect two different dinohomes, and every pair of two different dinohomes should be directly connected by at most one road.
Dinohomes are numbered from $1$ to $N$.
Sample Input 1 | Sample Output 1 |
---|---|
3 3 5 4 -1 -1 |
YES 1 2 1 3 3 2 NO |