When reading trough this forum there are a lot of posts/replies of the following form

```
The test cases for [Problem] are weak
```

Or if they have done a bit more work:

```
The test cases for [Problem] are weak
Here is a test case where most submissions fail on
```

I want to make a point to users making such statements: As a setter it is really hard to find such test cases beforehand. It is almost impossible to think about every wrong approach that might be taken. I am going to challenge you by putting you in the role of setter.

For my A&D class we had a practical assignment (in the first semester of last school year, so donâ€™t worry about me cheating). This assignment was based on an algorithm in a research paper, so I will not challenge you to find the algorithm. As far as I know none of the students, including me, found the algorithm of that paper. The algorithm I made did however pass all test cases, and I challenge you to make a test case for which my algorithm would fail.

# The problem â€śyou createdâ€ť

You are given a graph where each vertex has at most 4 neighbors. Find the maximum size of a set such that there is no edge connecting two vertices of that set.

or shorter:

Find the maximum independent set of a degree-4 graph.

# The solution â€śyou have come up withâ€ť

See https://link.springer.com/article/10.1007/s10878-017-0115-3 for the paper on the algorithm to solve the problem. I do not expect you to be able to read scientific papers.

# My solution

A setter would not have access to this solution.

# The challenge

Make a test case for which my algorithm will fails. The requirements for test cases are:

- It must be (easily) verifiable by hand.
- You must provide the expected answer
- The input has the form

```
N M
from_1 to_1
from_2 to_2
...
from_N to_N
```

where N (1\leq N\leq 200) is the number of *edges*, M (1\leq M\leq 100) the number of *vertices* (yes, this is backwards compared to what is standard in competitions; but that is how it was phrased for the assignment). and vertices are numbered 1-M. Edges are bidirectional. Self-loops are not allowed.

Full list of requirements of the test case:

- graph must be a simple graph; so no double edges between nodes
- graph may not contain self-loops
- each vertex of the graph must have at most 4 edges
- the number of edges (N) is at most 200 (and at least 1)
- the number of vertices (M) is at most 100 (and at least 1)
- from_i in between 1 and M
- to_i in between 1 and M

Post your test cases below, I will reply with the result of my algorithm; one of

- AC
- WA
- TLE (executed for more than one second)
- RTE (exception during execution)

And the output of the program in case of an AC or WA. I will grade test cases against the weakest version of my algorithm; although for the assignment I handed in a more robust version. Your goal is for me to receive one of the latter three verdicts on your text case.