以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。




可复制的 PDF 提取文本
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
Problem A. Parallel Universes
Input file: standard input
Output file: standard output
Time limit: 2 seconds
Memory limit: 512 megabytes
Berlandia — a country with a highly developed road system. There are a total of n cities in Berlandia,
and there is exactly one road between each pair of cities, accessible for travel in both directions.
For the purpose of saving electricity, only m1 roads are illuminated in Berlandia, the i-th of which connects
cities vi and ui. For safety reasons, it is forbidden to travel on unlit roads in Berlandia.
In a parallel universe, there is a similar country called Cherlandia, consisting of n cities. There is also
exactly one road between each pair of cities in Cherlandia. The countries differ only in their electricity
economy: in Cherlandia, m2 roads are illuminated, the i-th of which connects cities ai and bi. It is known
that in Cherlandia, it is possible to travel from any city to any other using only illuminated roads.
You possess a secret spell that allows you to choose any two different cities x and y and change the
illumination on the road between cities x and y in both universes. That is, in each universe, if the road
was not illuminated, it becomes illuminated, and vice versa.
You want to use this spell no more than n times in order to make it possible to travel from any city to
any other in Berlandia using only illuminated roads. At the same time, after each spell is cast, Cherlandia
must remain connected, that is, there should not exist two cities between which it is impossible to travel
on illuminated roads.
Determine if this can be achieved, and if so, find a suitable sequence of spells.
Input
Each test consists of several sets of input data. The first line contains two integers t and g (1 ≤t ≤60 000,
0 ≤g ≤10) — the number of sets of input data and the test group number. This is followed by descriptions
of the sets of input data.
The first line of each set of input data description contains three integers n, m1, and m2 (3 ≤n ≤300 000,
0 ≤m1, m2 ≤300 000, m1, m2 ≤n(n−1)2 ) — the number of cities, the number of illuminated roads in
Berlandia, and the number of illuminated roads in Cherlandia.
The next m1 lines contain descriptions of illuminated roads in Berlandia. The i-th line contains two
integers vi and ui (1 ≤vi, ui ≤n) — the numbers of cities connected by the i-th illuminated road. It is
guaranteed that all roads are distinct.
The next m2 lines contain descriptions of illuminated roads in Cherlandia. The i-th line contains two
integers ai and bi (1 ≤ai, bi ≤n) — the numbers of cities connected by the i-th illuminated road. It
is guaranteed that all roads are distinct, and that in Cherlandia, there exists a path consisting only of
illuminated roads between any two cities.
Let N, M1, and M2 be the sum of n, m1, and m2 for all sets of input data in one test. It is guaranteed
that N, M1, M2 ≤300 000.
Output
For each set of input data, output “No” (without quotes) if there is no sequence of spells that satisfies all
conditions.
Otherwise, output “Yes”. On the second line, output an integer k (0 ≤k ≤n) — the number of spells you
have used.
Then output k lines. In the i-th line, output two integers xi and yi (1 ≤xi, yi ≤n, xi ̸= yi) — the
numbers of cities to which the i-th spell is applied. Note that after each spell is cast, Cherlandia must
remain connected.
Page 1 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
Example
standard input standard output
3 0 No
3 0 3 Yes
1 2 1
2 3 2 4
1 3 Yes
4 2 3 2
1 2 1 2
3 4 4 2
1 3
1 4
2 3
4 3 3
1 2
2 3
1 3
1 4
2 4
3 4
Note
In the first set of input data, there is no suitable sequence of spells, so the answer is “No”.
In the second set of input data, the illuminated roads initially have the following structure:
1 2 1 2
4 3 4 3
Berlandia Cherlandia
After casting a spell on cities 2 and 4 in both Berlandia and Cherlandia, this road becomes illuminated,
as it was unlit in both countries. After this operation, the countries will have the following structure:
1 2 1 2
4 3 4 3
Berlandia Cherlandia
After this operation, it is possible to travel from any city to any other in Berlandia, so this sequence of
spells is correct.
In the third set of input data, after casting a spell on cities 1 and 2, the road between these two cities in
Berlandia ceases to be illuminated, as it was illuminated before. In Cherlandia, on the contrary, the road
becomes illuminated. After this operation, the countries will have the following structure:
Page 2 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
1 2 1 2
4 3 4 3
Berlandia Cherlandia
After casting a spell on cities 2 and 4, the countries will have the following structure:
1 2 1 2
4 3 4 3
Berlandia Cherlandia
Scoring
The tests for this problem consist of ten groups. Points for each group are given only if all tests of the
group and all tests of the required groups are passed. Please note that passing the example tests is not
required for some groups. Offline-evaluation means that the results of testing your solution on this
group will only be available after the end of the competition.
Additional constraints Required
Group Points Comment
Groups N, M1, M2
0 0 – – Examples.
1 9 N, M1, M2 ≤3000 – n ≤5
2 7 N, M1, M2 ≤3000 – m2 = n(n−1)2
Berlandia consists of two
3 10 N, M1, M2 ≤3000 – connected components1.
There are no
4 11 N, M1, M2 ≤3000 –
isolated2 cities in Berlandia.
m2 = n −1
5 15 N, M1, M2 ≤3000 –
ai = 1 and bi = i + 1 for all 1 ≤i ≤n −1
6 8 N, M1, M2 ≤3000 5 m2 = n −1
In both countries, the road between cities
7 12 N, M1, M2 ≤3000 –
1 and 2 is illuminated.
8 6 N, M1, M2 ≤3000 0 – 7
m2 = n −1
9 8 – –
ai = i and bi = i + 1 for all 1 ≤i ≤n −1
10 14 – 0 – 9 Offline-evaluation.
1 Connected component — a set of cities such that there exists a path consisting only of illuminated roads
between any pair of them.
Page 3 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
2 A city is called isolated if there is no illuminated road connecting it to any other city.
Page 4 of 12