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

Ancient texts record a mysterious ritual that can change the state of the light rails in the night sky. Specifically, each time the ritual is performed, you must choose exactly $k$ distinct stars, and then change the state of the light rails between these stars. Specifically, let the indices of the chosen stars be $s_0, \dots, s_{k-1}$. Then, for all $0 \le i < j \le k - 1$, if a light rail currently exists between star $s_i$ and star $s_j$, that light rail is removed; if it does not exist, a new light rail connecting them is added. Due to limited materials for the ritual, this ritual can be performed at most $p$ ($p \ge n(n - 1)/2$) times.

When there are more light rails, the night sky becomes more brilliant. You need to find the maximum number of light rails in the night sky after performing at most $p$ rituals, and provide a corresponding sequence of rituals if 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"

You need to implement the following two functions in your submitted source file starmap.cpp:

void init(int c, int t);

• $c$ and $t$ represent the test case ID and the number of test data groups, respectively. $c = 0$ indicates that this test case is a sample.
• For each test case, this function will be called exactly once by the interactor when the program starts.

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

• $n, m, k, p$ represent the number of stars, the number of light rails, the number of stars chosen for the ritual, and the limit on the number of rituals, respectively.
• For $0 \le i < m$, $u_i, v_i$ represent the two stars connected by the $i$-th light rail initially.
• For each test case, this function will be called exactly $t$ times by the interactor.

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

void report(int c);

• $c$ represents the maximum number of light rails.
• You must ensure that the interactor calls starmap exactly once.

You can perform a ritual by calling the following function:

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

• $s_0, \dots, s_{k-1}$ represent the $k$ chosen 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 distinct.
• You must ensure that for each call to starmap by the interactor, this function is called at most $p$ times, and all calls to this function occur after the call to the report function.

Note: In any case, the total execution time of the interactor during final testing will not exceed 4.5 seconds, and the memory used is fixed and will not exceed 64 MiB.

Constraints

Let $N$ be the sum of $n$ over all test data in a single test case. For all test data:

• $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 distinct.

Examples

Input 1

0 1
4 2 2 20
1 2
2 3

Output 1

6 1

Input 2

0 1
6 1 3 20
1 2

Output 2

13 1

Note

• Example 3: See starmap/starmap3.in and starmap/starmap3.ans in the contestant directory. This example satisfies the constraints for test cases 3 and 4.
• Example 4: See starmap/starmap4.in and starmap/starmap4.ans in the contestant directory. This example satisfies the constraints for test cases 5 $\sim$ 7.
• Example 5: See starmap/starmap5.in and starmap/starmap5.ans in the contestant directory. This example satisfies the constraints for test cases 8 $\sim$ 10.
• Example 6: See starmap/starmap6.in and starmap/starmap6.ans in the contestant directory. This example satisfies the constraints for test cases 11 $\sim$ 13.
• Example 7: See starmap/starmap7.in and starmap/starmap7.ans in the contestant directory. This example satisfies the constraints for test cases 17 $\sim$ 20.
• Example 8: See starmap/starmap8.in and starmap/starmap8.ans in the contestant directory. This example satisfies the constraints for test cases 21 $\sim$ 25.

Scoring

Note: Contestants should not obtain internal information of the interactor through illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating. The final evaluation interactor is different from the sample interactor.

This problem is subject to the same restrictions as traditional problems, such as compilation errors resulting in 0 points for the entire problem, and runtime errors, time limit exceeded, or memory limit exceeded resulting in 0 points for the corresponding test case. Contestants can only access variables defined by themselves and variables provided by the interactor; attempting to access other address spaces may lead to compilation or runtime errors.

Each time the starmap function is called, if the report or invert function is called illegally, or if the invert function is called more than $p$ times, the corresponding test case will receive 0 points.

Based on the above conditions: For each test case, if the maximum number of light rails reported by the report function is correct, you can receive 25% of the points. On this basis, if the number of light rails after performing all rituals is equal to the maximum value, you can receive full marks. * Note: If the reported maximum number of light rails is correct, but the number of invert function calls exceeds $p$, you will still receive 0 points.