The task of this year’s challenge is to compute a crossing-minimal two-layer layout of a given bipartite graph $G=((A\dot\cup B),E)$ with a fixed linear order on the vertices of $A$.

## The Input Format

The graph is presented as input in essentially the same graph (`.gr`

) format used in previous iterations of the challenge:

- The
*line separator*is`\n`

. - A line starting with
`c`

is a*comment*and has no semantics. - The first non-comment line is the
*p-line*:- It is formatted as
`p ocr n0 n1 m`

, where `ocr`

the*problem descriptor*;`n0`

is the number of vertices in bipartition $A$ (the fixed partition);`n1`

is the number of vertices in bipartition $B$ (the free partition);`m`

the number of edges to follow.

- It is formatted as
- The p-line is unique and no other line starts with
`p`

. - The vertices in $A$ are numbered from $1$ to $n_0$, the vertices in $B$ are numbered from $n_0+1$ to $n_0+n_1$.
- After the p-line there will be exactly
`m`

non-comment lines that encode the edges:- These are formatted as
`x y`

and define an edge between $x$ and $y$, where $x$ is a number between $1$ and $n_0$, and $y$ is a number between $n_0+1$ and $n_0+n_1$.

- These are formatted as

Here is an example:

```
c this is a comment
p ocr 3 3 3
1 5
2 4
3 6
```

For the parameterized track, the p-line contains an additional parameter `cw`

that gives the cutwidth of the graph.
The first line is then formatted as ‘p ocr n0 n1 m cw’
The first $n_0+n_1$ lines then list a total order of the vertices attaining this cutwidth.

```
c this is a comment
p ocr 3 3 3 1
1
5
2
4
6
3
1 5
2 4
3 6
```

## Output Format

In the output, we only expect the second bipartition for the $n_1$ vertices of $B$ to be encoded. The $n_0$ vertices of $A$ are assumed to be placed along a line in ascending order. Hence, the output file contains just $n_1$ numbers separated by newlines.

```
5
4
6
```

## Verifier

We provide a verifier to check whether a given linear order is valid for a given graph. The output will either be the number of crossings or an error message.

## Autotester

We will provide a repository that contains a script to automatically test your implementation on a set of instances and solutions, together with a public test set (TBA December 2024).