22376번 - Aggressive Traveller 다국어

You are very eager to travel to many countries. There are $N$ countries in the world. $M$ distinct pairs of the countries have a travel route between the two countries. All the $M$ routes are one-way: if there is a route from $A$ to $B$, you can move from country $A$ to country $B$, but not from $B$ to $A$ unless there is another route from $B$ to $A$. Now you are in country $S$ and set the goal of your travel to country $T$. From $S$ to $T$, you want to visit the countries as many times as possible.

However, there are some restrictions. There are $K$ countries which have strict security checks before you enter these countries. The flow of the security check of the $i$-th restricted country $c_i$ is as follows:

1. You show your passport to an officer.
2. The officer checks your passport. If at least one of the following two conditions is satisfied, your entrance is rejected:
   1. Your passport has two or more stamps of the same country.
   2. Your passport has more than $r_i$ stamps.
3. Otherwise your entrance is accepted. The officer stamps your passport with a stamp of country $c_i$.
4. You enter the country $c_i$.

Note that in $N-K$ countries other than $K$ restricted countries, passport checking is skipped so you can freely enter these countries but you must get a stamp of a country you enter. Also notice that you may be able to enter $c_i$ at most twice, because you get a stamp after passport checking. Initially your passport has only a single stamp of country $S$.

As an aggressive traveller, you want to maximize the number of stamps on your passport. You are going to start your travel from country $S$ and eventually finish the travel at country $T$. Write a program that outputs the maximum number of stamps you can get on your passport when you reach $T$. This number includes the stamps of countries $S$ and $T$. If you cannot reach $T$ from $S$, output 'UNREACHABLE' instead. Also, if you can indefinitely repeat to visit countries and then eventually reach $T$, output 'INFINITY' instead. Note that you don't have to stop your travel when reaching $T$ and can visit $T$ multiple times.

The input consists of a single test case in the format below.

$N$ $M$ $K$ $S$ $T$

$u_1$ $v_1$

$\vdots$

$u_M$ $v_M$

$c_1$ $r_1$

$\vdots$

$c_K$ $r_K$

The first line contains five integers $N$ ($3 \le N \le 1,000$), $M$ ($2 \le M \le 10,000$), $K$ ($1 \le K \le N$), $S$ ($1 \le S \le N$), $T$ ($1 \le T \le N$). $N$ is the number of countries. $M$ is the number of routes between pairs of countries. $K$ is the number of restricted countries. $S$ and $T$ are the countries you start your travel from and want to reach, respectively. The $i$-th of following $M$ lines is the information of the $i$-th route: you can move from countries $u_i$ to country $v_i$ ($1 \le u_i, v_i \le N$). The $j$-th of further following $K$ lines is the information of the $j$-th restricted country: country $c_j$ ($1 \le c_j \le N$) has the limit $r_j$ ($1 \le r_j \le 5$) of the number of stamps on your passport.

You can assume:

• $S \le T$,
• no self-loop, i.e. $u_i \ne v_i$ for $1 \le i \le M$,
• no duplicate routes, i.e. $u_i \ne u_j$ and/or $v_i \le v_j$ for $1 \le i < j \le M$,
• no duplicate restricted countries, i.e. $c_i \ne c_j$ for $1 \le i < j \le K$, and
• countries $S$ and $T$ are not restricted, i.e. $c_j \ne S$ and $c_j \le T$ for $1 \le j \le K$.

Output the maximum number of stamps you can get on your passport during your travel from $S$ to $T$. If you cannot reach $T$ from $S$, output 'UNREACHABLE'. If you can get an infinite number of stamps on your passport, output 'INFINITY'.