시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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'.

예제 입력 1

4 5 1 1 4
1 2
1 3
2 1
2 3
3 4
3 2

예제 출력 1

4

예제 입력 2

3 3 1 1 2
1 2
1 3
3 1
3 5

예제 출력 2

4

예제 입력 3

4 2 2 1 4
1 2
3 4
2 5
3 5

예제 출력 3

UNREACHABLE

예제 입력 4

4 4 1 1 4
1 2
2 3
3 2
3 4
2 3

예제 출력 4

6

예제 입력 5

4 4 1 2 3
2 1
1 3
3 4
4 3
1 1

예제 출력 5

INFINITY

예제 입력 6

4 4 1 1 3
1 2
2 3
3 4
4 3
4 5

예제 출력 6

5

예제 입력 7

6 7 1 1 6
1 2
2 3
3 1
3 4
4 5
5 6
6 4
3 5

예제 출력 7

INFINITY

예제 입력 8

6 7 1 1 6
1 2
2 3
3 1
3 4
4 5
5 6
6 4
4 5

예제 출력 8

6

예제 입력 9

7 6 5 1 7
1 2
2 3
3 4
4 5
5 6
6 7
2 1
3 2
4 3
5 4
6 4

예제 출력 9

UNREACHABLE

예제 입력 10

4 4 1 1 4
1 2
2 3
3 1
2 4
3 2

예제 출력 10

6