% topic: graph theory
% difficulty: any
% usage: creative task - round 1
% author: daniel/sam

% For the visualization at the SOI-day we can use various hand-drawn graphs 
% and lay them on top of real cities, like Zurich, London, Taipei, etc.

% Two possibilities concerning several cops on same junction:
% a) Two cops can never be on the same junction at the same time, and 
%    cops move one after the other, in a given order (which is always the same).
%    Scotland Yard board game works like this, and this is sometimes quite a
%    challenge for the cops.
% b) On each junction, there may be any number of cops. Much easier to implement.
%    Since the order in which cops move does not matter, we can say that they
%    move simultaneously.
% We choose b) because it's easier to implement.

% Two possiblities concerning staying on the same junction:
% a) Staying on the same junction is a valid move.
% b) It's not allowed (Scotland Yard board game).
% We choose a) because it gives more possibilities/freedom.


\bigcaption{Cops and Robbers}

Mouse Stofl was asked by Scotland Yard to help find and arrest the dangerous Mouse X.
Your job is to direct the cops through the streets of London to make sure that there
is no way for Mouse X to escape. 
Or do you feel adventurous? You can also help Mouse X to avoid the cops as long as
possible.

\caption{The Game}

The city is modelled as a graph consisting of $N$ junctions and $M$
streets, each of which connects two different junctions.
Between any given pair of two junctions, there is at most one street,
% (most programs won't need that it's a simple graph, but we still guarantee it, 
% just in case)
and each street can be used in both directions.
The graph is connected, i.e. for any two junctions, it is possible to get from the
first junction to the second using a sequence of streets.

There are $C+1$ mice. One of them is Mouse X and is controlled by the first program,
and the remaining $C$ are cops and controlled by the second program.

At the beginning of the game, the mice are distributed randomly over the junctions.
It is guaranteed that no two mice start on the same junction, and that no two
mice start on neighboring junctions (i.e. two junctions connected by a street).

The game is played in rounds. 
In each round, Mouse X moves first and after that all cops move simultaneously.
The following are valid moves:
\begin{itemize}
\item Move to a neighboring junction.
\item Stay on the same junction.
\end{itemize}
Note that it is allowed to have several cops on the same junction at the same time.

The game ends as soon as one of the following happens:
\begin{itemize}
\item Mouse X moves on a junction occupied by one or several cops. 
      In this case, the cops win.
\item A cop moves on the junction where Mouse X is. In this case, the cops win.
\item $R$ rounds have been played without Mouse X being caught. 
      In this case, Mouse X wins.
\end{itemize}


\caption{Input and Output}

Your program will be run by a game server. 
It has to read from stdin and has to output its moves to stdout.

When the game starts, you are given a line containing the letter ``P'' (for police)
if you have to play the cops or ``X'' if you have to play Mouse X.

After that, you get a line containing the integer $C$, followed by a line
containing the integer $R$.

Then you are given the street graph of the city in the following format:
One line containing two integers $N$ and $M$, separated by a single space, followed
by $M$ lines, each of which contains two integers $a_i$ and $b_i$ which indicate
that there is a street between junction $a_i$ and junction $b_i$. 
Junctions are numbered from $1$ to $N$, and $1 \leq a_i, b_i \leq N$.

Then, you read the initial position(s) of your player(s): 
If you're Mouse X, that's a line containing one junction number, and
if you're the cops, it's a line containing $C$ space-separated junction numbers,
the $i$-th number being the initial junction of the $i$-th cop. 
Note that the order of the cops in the input remains the same throughout the whole game.
Then, round after round is played.

\noindent If you're Mouse X, a round works as follows:
\begin{enumerate}
\item You get a line containing $C$ space-separated integers, indicating on which
      junctions the cops currently are.
\item You have to output one integer, the number of the junction to which you want
      to move.
\end{enumerate}

\noindent If you're the cops, a round works as follows:
\begin{enumerate}
\item You get a line containing one integer, indicating on which
      junction Mouse X currently is.
\item You have to output $C$ space-separated integers, the $i$-th number being
      the number of the junction to which you want to move the $i$-th cop.
\end{enumerate}

Once the game is ended, your program will be terminated by the server.


\caption{Sample communication}
An example of a game is illustrated in the figure. Below you can find the corresponding communication for the Mouse X and the cops.
\begin{figure}
\includegraphics[width=\textwidth]{figures/copsandrobbersexample}
\label{example}
\caption{Example game.}
\end{figure}

\paragraph*{Mouse X communication}
\begin{verbatim}
> X
> 2
> 100
> 7 7
> 1 2
> 1 3
> 2 4
> 3 4
> 3 5
> 5 6
> 5 7
> 3
> 6 7
< 1
> 5 5
< 2
> 3 3
< 2
> 4 1
< 4
\end{verbatim}

\paragraph*{Cops communication}
\begin{verbatim}
> P
> 2
> 100
> 7 7
> 1 2
> 1 3
> 2 4
> 3 4
> 3 5
> 5 6
> 5 7
> 6 7
> 1
< 5 5
> 2
< 3 3
> 2
< 4 1
\end{verbatim}

%Some samples:
%A tree where the cops win
%A circle where the robber wins


\caption{Limits}

% Note: Limits are subject to change/discussion.

\begin{itemize}
\item $1 \leq C \leq 8$
\item $10 \leq R \leq 100$
\item $10 \leq N \leq 200$
\item $10 \leq M \leq 500$
\end{itemize}


\caption{Tips}

For interactive tasks, it is important that you flush the output buffer after 
every round to make sure that your output becomes visible for the server. 
Use the following commands:
\begin{itemize}
\item C/C++: \verb|fflush(stdout);|
\item C++: \verb|cout << flush;|
\item Pascal: \verb|flush(output);|
\item In other languages, similar commands exist.
\end{itemize}

Further, when reading input, it is important that your program does not wait for 
more characters than the server gives you as input. 
Especially spaces or line breaks in the format string in C are a common cause of error.
For instance, if you read the last variable of the input with \verb|scanf("%d ", &x);|,
the scanf function waits for the next character which is not a space or a newline. 
However, you will get such a character only after you have announced your move. 
So, your program would block here. 
To solve this, use \verb|scanf("%d", &x);| instead, i.e. no whitespace after the
\verb|%d|.


\caption{Sample Bots, server and visualization}

\noindent During the first round, we will provide the following material:
\begin{itemize}
\item Sample bots in different programming languages.
\item A server program that you can use to let your own program compete against 
      your and other programs.
\item A visualization to animate simulated games.
\end{itemize}
You will find this material here (link not yet available), 
and since they are continuously developed, 
it is worth having a look at the website from time to time.


\caption{Grading}

The grading scheme for the creativity task is different than 
for the other tasks. You get:

\begin{itemize}
\item 50\% of the points for a program which plays the game correctly,
      i.e. which respects all the rules and plays at least as well as the sample bots. 
      Important: You are not allowed to simply copy and submit the code of the sample
      bots. 
      However, you are allowed and encouraged to use them as instructions on how to 
      correctly do the input/output in your programming language. 
\item The remaining 50\% of the points are awarded according to the result at the
      tournament at the SOI day.
\end{itemize}


