Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 1079 (Div. 1)
F. Indivisible Finished
time limit per test: 2 seconds
memory limit per test: 256 megabytes → Virtual participation
You are given two numbers n and m. Virtual contest is a way to take part in past
contest, as close as possible to participation
on time. It is supported only ICPC mode for
An undirected graph is called beautiful if it satisfies the following conditions: virtual contests. If you've seen these
problems, a virtual contest is not for you -
It has no loops or multiple edges. solve these problems in the archive. If you
just want to solve some problem from a
It has exactly n vertices and m edges. contest, a virtual contest is not for you -
Its vertices cannot be divided into 2 sets such that the sums of the degrees of all vertices in the first set and the sums of the degrees of solve this problem in the archive. Never use
someone else's code, read the tutorials or
all vertices in the second set are equal. communicate with other person during a
virtual contest.
You need to either report that a beautiful undirected graph with the given n, m does not exist, or provide one.
Start virtual contest
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1
4
≤ t ≤ 10 ). The description of the test cases
follows. → Problem tags
5 5
n(n−1) brute force constructive algorithms
The only line of each test case contains two integers n, m (12 ≤ n ≤ 10 , 1 ≤ m ≤ min(2 ⋅ 10 ,
2
) ) — the number of vertices
graphs
and edges in the graph.
No tag edit access
5
It is guaranteed that the sum of n across all test cases does not exceed 10 , and the sum of m across all test cases does not exceed
2 ⋅ 10 .
5
→ Contest materials
Output Announcement
For each test case, output "No" if such a graph does not exist. Otherwise, output "Yes", and then, in the following m lines — the edges
of the beautiful graph in arbitrary order. If there are multiple answers, you may output any of them.
Example
input Copy
5
12 7
12 1
90000 12
30 434
30 435
output Copy
Yes
1 2
2 3
3 4
4 5
5 1
1 3
2 4
No
Yes
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
No
No
Note
In the first test case, the graph is a simple cycle of 7 vertices. The degrees of the vertices are {2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0} . It is easy to
see that in such a graph, it is impossible to divide the vertices into 2 parts with equal sums of degrees.
In the second test case, since m = 1 , it is easy to see that the vertices can always be divided into 2 parts with equal sums of degrees.
Therefore, no solution exists.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Feb/12/2026 17:27:36UTC+5.5 (g1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by