← 返回题目列表

Codeforces · 2080/A

A. 强大的连接性反击

中文机器翻译题面 查看原题

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

Strong Connectivity Strikes Back - 原题 PDF 第 1 页
原题PDF第1页
Strong Connectivity Strikes Back - 原题 PDF 第 2 页
原题PDF第2页
Strong Connectivity Strikes Back - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
Open Olympiad in Informatics 2024/25. Second day
                                  Moscow, March 8th, 2025
Problem Wool. Strong Connectivity Strikes Back

     Input file:         input.txt or standard input
    Output file:       output.txt or standard output
    Time limit:        1 second
    Memory limit:     512 megabytes

Vertices u and v of a directed graph are called strongly connected if there exists a path from u to v and
a path from v to u in the graph. Note that if u and v are strongly connected, and v and w are strongly
connected, then u and w are also strongly connected. Therefore, the vertices of the graph are divided into
sets—strongly connected components. A vertex belonging to a strongly connected component is strongly
connected to all vertices in the component (including itself) and is not strongly connected to any vertices
outside the component.

During a graph class, Alice drew a directed graph with n vertices on the board and highlighted its strongly
connected components. During the break, Bob decided to play a trick on Alice and erase the directions
on some edges of the graph. He wants Alice to be able to uniquely restore the erased directions based on
the remaining edges and the partition into strongly connected components after the break.

Help Bob by determining the maximum number of edges in the graph whose directions he can erase, as
well as the number of ways he can do this.

More formally, find the maximum size of a subset of edges A that has the following property:  if the
directions of the edges in the set A are erased, then based on the information about the old strongly
connected components and the directions of the edges not in the set A, the directions of the edges in the
set A can be uniquely restored in such a way that the strongly connected components remain unchanged.
Since the number of such maximum subsets can be very large, output it modulo 109 + 7.

Solutions that correctly determine the maximum size of the set A but incorrectly present the number of
such subsets will receive partial points.

Input

The first line contains three integers n, m, and g (2 ≤n ≤2000, 1 ≤m ≤2000, 0 ≤g ≤7)—the number
of vertices and edges in the graph, respectively, as well as the test group number.

The next m lines contain two integers ui and vi (1 ≤ui, vi ≤n, ui ̸= vi)—the numbers of the vertices
that are the start and end of the i-th edge.

It is guaranteed that for any 1 ≤i, j ≤n (ui, vi) ̸= (uj, vj) and (ui, vi) ̸= (vj, uj), meaning that any two
vertices are connected by at most one edge, regardless of direction.

Output

In the first line, output a single number—the size of the maximum subset of edges whose directions can
be erased.
In the second line, output a single number—the number of such subsets modulo 109 + 7. If you do not
want to present the number of such subsets, then in the second line, instead, output any number from −1
to 109 + 6. In this case, your solution will receive partial points for the test.

Note that omitting any number in the second line leads to a verdict of "Wrong Answer"and zero points
for this test, regardless of the correctness of the size of the subset.





                                         Page 1 of 11

Open Olympiad in Informatics 2024/25. Second day
                                  Moscow, March 8th, 2025

Example

                  input                                   output
 5 6 0                                   3
 1 2                                     3
 1 5
 2 3
 3 4
 3 5
 4 2

Note

The graph from the example with strongly connected components highlighted:



                                   1         2


                                                       4


                                   5         3



The directions on the dashed edges can be removed. Indeed, the edge (1, 5) cannot be oriented in the
opposite direction, because otherwise, vertices 1, 2, 3, and 5 would belong to the same strongly connected
component. The edges (3, 4) and (4, 2) cannot be oriented differently either, because then vertices 2, 3,
and 4 would not belong to the same strongly connected component.

Now, let’s consider an incorrect way of selecting a subset of edges:



                                   1         2


                                                       4


                                   5         3



Here, the directions on the bold dashed edges cannot be removed. For example, if we reverse the orientation
of edges (1, 2) and (1, 5), we get a graph with the same decomposition into strongly connected components.

It can be shown that the directions on exactly 4 edges cannot be removed, so the answer is 3.

Scoring

The tests for this problem consist of seven groups. The rules for scoring the subgroups are described
below.

If the size of the maximum subset of edges whose directions can be erased and the number of such subsets
are correctly calculated in all tests of the group, full points are awarded for the group.

Otherwise, if the size of the maximum subset of edges whose directions can be erased is correctly calculated
in all tests of the group, but the number is incorrect in at least one test of the group, partial points are
awarded for the group. Note that dependent groups will be tested in this case and may even be scored
full points.




                                         Page 2 of 11

Open Olympiad in Informatics 2024/25. Second day
                              Moscow, March 8th, 2025

            Points      Additional Constraints   Required
Group                                                    Comment
                                           Groups         Partial   Full    n      m

  0       0      0      –          –            –                   Examples.

  1       7      11   n ≤14   m ≤14         0

  2       5      9   n ≤20   m ≤20          0, 1

                                                                   ui < vi, for all 1 ≤i ≤n −1 there is
  3       8      12      –          –            –
                                                              an edge (i, i + 1)

  4       8      13      –          –            3                        ui < vi

                                                                       for all 1 ⩽i ⩽n −1 there is an edge
  5       12     20      –          –            –
                                                                                        (i, i + 1), there is an edge (n, 1)

                                                               the graph consists of one strongly
  6       13     21      –          –            5
                                                                  connected component

  7       8      14      –          –          0 – 6





                                    Page 3 of 11