|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
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:
- All the routes start at city $F$.
- All the routes end at city $M$.
- There are no routes with repeated cities.
- For every pair of routes the only cities in common are $F$ and $M$ (there are no repeated internal cities among the routes).
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.
Input
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$.
Output
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.
Sample test(s)
Input
4 4 1 4 2
1 2
1 3
2 4
3 4
Output
FITO
2
2 3
Input
4 4 1 4 1
1 2
1 3
2 4
3 4
Output
MARIA
2
3 1 3 4
3 1 2 4