Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito and María were playing with a map of the kingdom of Sigma. The map consists of $N$ cities and roads between pairs of cities (roads can be used in any direction). At the start of the game, the kids selected two cities: Fito chose city $F$ while María picked city $M$. The kids were very careful in their choices: the cities were distinct and were not connected by a road. They decided to solve different challenges.

Given $K$, Fito wants to find at most $K$ cities (different from $F$ and $M$) such that if they are removed from the map along with the roads incident to the removed cities, then there isn't any route between city $F$ and city $M$.

On the other hand, María wants to find at least $K+1$ routes such that:

Help any of the children find the answer to his/her question.

Note: There may exist multiple roads between the same pair of cities, and roads between a city and itself.

One line with five integers $N$, $T$, $F$, $M$, $K$ ($1 \le N, T, K \le 10^5$, $1 \le F, M \le N$). The number of cities, the number of roads, the city selected by Fito, the city selected by María and the picked number respectively.

Then $T$ lines with two integers $u$, $v$ ($1 \le u, v \le N$) denoting an undirected road between cities $u$ y $v$.

If you find a solution for Fito, print in the first line the word $\texttt{"FITO"}$ without quotes. In the second line print a number $C$ ($0 \le C \le K$), the amount of cities that Fito has to remove to solve his challenge. Then print a line with $C$ positive integers $u$ ($1 \le u \le N$), the cities he will remove. Any valid answer will be accepted.

If you find a solution for María's challenge, print in the first line the word $\texttt{"MARIA"}$ without quotes. In the next line print number $C$ ($K + 1 \le C \le N$), the amount of paths María will pick. In the following $C$ lines print each path using the described format. First print the number $X$ of cities in the path and next $X$ integers $u$ ($1 \le u \le N$), the cities. Each path must obey restrictions stated above. Read second test cases for more details.

You just have to find an answer for at most one of the two children. In case none of the challenges has any solution, print $\texttt{"NONE"}$ without quotes.