Background

What a star map lays out may not be the way home.

But if someone follows it, they are not lost.

---

Submission notes:

1. Do not include any header files.
2. Paste the following content at the top of the file:

   #include <vector>
   void init(int, int);
   void report(int c);
   void invert(std::vector<int>);
   

3. Submit using C++ 17 / 20.

Problem Description

There are $n$ stars in the night sky, numbered $1 \sim n$. Initially, there are $m$ light trails in the sky. The $i$-th ($0 \le i < m$) light trail connects stars $u_i$ and $v_i$.

An ancient book records a mysterious ritual that can change the state of the light trails in the sky. Specifically, each time you perform the ritual, you must choose exactly $k$ distinct stars, and then toggle the states of the light trails between these stars. More precisely, let the chosen stars be $s_0, \dots, s_{k-1}$. For all $0 \le i < j \le k-1$, if there is currently a light trail between $s_i$ and $s_j$, it will be deleted; otherwise, a new light trail connecting them will be added. Since the ritual materials are limited, this ritual can be performed at most $p$ times ($p \ge n(n-1)/2$).

With more light trails, the night sky becomes more brilliant. You need to find the maximum possible number of light trails after performing at most $p$ rituals, and provide a corresponding ritual plan as much as possible.

【Implementation Details】

You do not need to, and should not, implement the main function.

You must ensure that your submitted program includes the header file starmap.h, i.e., add the following code at the beginning of your program:

#include "starmap.h"

In your submitted source file starmap.cpp, you need to implement the following two functions:

void init(int c, int t);

• $c, t$ denote the test point ID and the number of testdata groups. $c = 0$ means this test point is the sample.
• For each test point, this function will be called by the interactive library exactly once when the program starts running.

void starmap(int n, int m, int k, int p, std::vector<int> u, std::vector<int> v);

• $n, m, k, p$ denote the number of stars, the number of light trails, the number of stars chosen in each ritual, and the limit on the number of rituals.
• For $0 \le i < m$, $u_i, v_i$ denote the two stars connected by the $i$-th light trail initially.
• For each test point, this function will be called by the interactive library exactly $t$ times.

You can report the maximum number of light trails by calling the following function:

void report(int c);

• $c$ is the maximum number of light trails.
• You must ensure that during each call to starmap, this function is called exactly once.
• You can perform one ritual by calling the following function:

void invert(std::vector<int> s);

• $s_0, \dots, s_{k-1}$ are the chosen $k$ stars. You must ensure that the length of $s$ is $k$, and for all $0 \le i \le k - 1$, $1 \le s_i \le n$, and $s_0, \dots, s_{k-1}$ are pairwise distinct.
• You must ensure that for each call to starmap, the number of calls to this function does not exceed $p$, and all calls to this function are made after calling report.

Note: In all cases, during the final test, the time needed for the interactive library to run will not exceed $4.5$ seconds, the memory used is fixed-size, and will not exceed $64$ MiB.

【How to Run the Testing Program】

grader.cpp in the problem directory is a reference implementation of the interactive library. The interactive library used in the final test is different from this reference implementation, so your solution should not depend on the interactive library implementation.

You can compile an executable in this directory using the following command:

g++ grader.cpp starmap.cpp -o starmap -std=gnu++14 -O2 -static

Input Format

For the compiled executable:

• The executable will read input from standard input in the following format:
  • The first line contains two non-negative integers $c, t$, representing the test point ID and the number of testdata groups.
  • Then follow $t$ groups of testdata. For each group:
    • The first line contains four positive integers $n, m, k, p$, representing the number of stars, the number of light trails, the number of stars chosen in each ritual, and the limit on the number of rituals.
    • Line $i + 2$ ($0 \le i < m$) contains two non-negative integers $u_i, v_i$, representing the two stars connected by the $i$-th light trail initially.

Output Format

• The executable will output the following format to standard output:
  • For each testdata group, output one line with two non-negative integers, representing the maximum number of light trails and whether the number of light trails after performing all rituals equals the maximum.

This problem has two subtasks. If you answer the first subtask correctly, i.e., the maximum number of light trails reported by the report function is correct, you can get partial score. For detailed scoring rules, see 【Scoring Method】.

0 1
4 2 2 20
1 2
2 3

6 1

0 1
6 1 3 20
1 2

13 1

Hint

【Sample 3】

See starmap/starmap3.in and starmap/starmap3.ans in the contestant directory.

This sample satisfies the constraints of test points $3, 4$.

【Sample 4】

See starmap/starmap4.in and starmap/starmap4.ans in the contestant directory.

This sample satisfies the constraints of test points $5 \sim 7$.

【Sample 5】

See starmap/starmap5.in and starmap/starmap5.ans in the contestant directory.

This sample satisfies the constraints of test points $8 \sim 10$.

【Sample 6】

See starmap/starmap6.in and starmap/starmap6.ans in the contestant directory.

This sample satisfies the constraints of test points $11 \sim 13$.

【Sample 7】

See starmap/starmap7.in and starmap/starmap7.ans in the contestant directory.

This sample satisfies the constraints of test points $17 \sim 20$.

【Sample 8】

See starmap/starmap8.in and starmap/starmap8.ans in the contestant directory.

This sample satisfies the constraints of test points $21 \sim 25$.

【Description of Provided Files】

In this problem directory:

1. grader.cpp is the provided reference implementation of the interactive library.
2. starmap.h is the header file; contestants do not need to care about its details.
3. template_starmap.cpp is the provided sample code; contestants may refer to it and implement their own code.

Contestants should back up all provided files carefully. In the final evaluation, only starmap.cpp in this problem directory will be tested. Any changes to files other than this program will not affect the evaluation result.

【Constraints】

Let $N$ be the sum of $n$ over all testdata within a single test point. For all testdata, we have:

• $1 \le t \le 10$.
• $4 \le n \le 500$, $N \le 3,000$.
• $0 \le m \le n(n-1)/2$, $2 \le k \le n-2$, $n(n-1)/2 \le p \le 2 \times 10^5$.
• For all $0 \le i \le m-1$, $1 \le u_i < v_i \le n$, and $(u_0, v_0), \dots, (u_{m-1}, v_{m-1})$ are pairwise distinct.

::cute-table{tuack}

Test point ID	$n \le$	$k$	$p =$
$1,2$	$8$	$\le n-2$	$500$
$3,4$	$18$	^
$5 \sim 7$	$500$	$= 3$	$n(n-1)/2$
$8 \sim 10$	$70$	$\le n-2$	^
$11 \sim 13$	$500$	$\le 70$
$14 \sim 16$	$300$	$\le n-2$	$2n^2 + 5n$
$17 \sim 20$	$400$	^	$n^2 + 10n$
$21 \sim 25$	$500$		$n(n-1)/2$

【Scoring Method】

Notes:

• Contestants must not obtain internal information of the interactive library by illegal means, such as interacting directly with standard input/output streams. Such behavior will be considered cheating.
• The interactive library used in the final evaluation is different from the sample interactive library implementation.

This problem is first subject to the same limits as traditional problems. For example, compilation errors will result in $0$ points for the entire problem; runtime errors, exceeding the time limit, exceeding the memory limit, etc., will result in $0$ points for the corresponding test point. Contestants may only access variables defined by themselves and variables provided by the interactive library. Attempting to access other address spaces may cause compilation errors or runtime errors.

For each call to the starmap function, if the call to report or invert is invalid, or if the number of calls to invert exceeds $p$, then the corresponding test point will receive $0$ points.

On top of the above conditions:

• For each test point, if the maximum number of light trails reported by report is correct, you can get $25\%$ of the score.
• On this basis, if after performing all rituals, the number of light trails equals the maximum, you can get full score.
• Note: If the maximum number of light trails reported is correct, but the number of calls to invert exceeds $p$, you will still get $0$ points.

Translated by ChatGPT 5