돈 복사

GIST 하우스 중고장터는 돈을 특정 물건으로 바꾸거나, 특정 물건을 다른 특정 물건으로 바꾸는 이벤트를 진행한다. 물건끼리 바꿀 때는 돈이 추가로 오갈 수도 있다. 중고장터는 돈과 물건을 무한히 가지고 있으므로, 모든 거래는 재화가 남아 있는 한 무한히 반복할 수 있다. 단, 고객은 한 번에 물건을 최대 하나까지만 들고 있을 수 있다.

예를 들어 다음 거래들이 존재한다고 하자.

• $t_1$: 사용자가 $1$번 물건을 $10$원에 산다.
• $t_2$: 사용자가 $1$번 물건에 $10$원을 더해 $2$번 물건과 교환한다.
• $t_3$: 사용자가 $2$번 물건을 팔고 $21$원을 받는다.
• $t_4$: 사용자가 $2$번 물건을 $1$번 물건과 교환하고 $12$원을 추가로 받는다.
• $t_5$: 사용자가 $2$번 물건을 $7$원에 산다.

이 중 개발팀이 리스트 $L_1 = \{t_1, t_2, t_3\}$에 든 거래만 허용한다고 하자. 그러면 $t_1, t_2, t_3$를 이 순서로 선택해 $20$원을 $21$원으로 늘릴 수 있다. 이를 무한히 반복하면 돈을 무한정 늘릴 수 있다. 돈이 이렇게 복사되면 대한민국 경제에 악영향을 끼칠 수 있어서, 개발팀은 이를 막고 싶어 한다. 따라서 개발팀은 거래 리스트가 주어지면 그 리스트가 안전한지 판별하려 한다.

리스트의 안전도는 다음과 같이 정의된다.

• 어떤 사람이 $C$원을 초기 자금으로 갖고 거래를 반복하여 돈을 무한정 늘릴 수 있다면, 리스트의 안전도는 $C$의 최솟값이다. 그러한 $C$가 존재하지 않으면 리스트의 안전도는 $\infty$이다. 이때 돈을 늘리기 위해 모든 물건을 팔 필요는 없다.

예를 들어 리스트 $L_1 = \{t_1, t_2, t_3\}$의 안전도는 $20$이다. $20$원을 가지고 $t_1, t_2, t_3$를 차례로 고르기를 반복하면 되기 때문이다. 그러나 $19$원을 가진 사람은 어떻게 해도 돈을 무한정 늘릴 수 없다. 또 리스트 $L_2 = \{t_3, t_4, t_5\}$의 안전도는 $7$이다.

한편 리스트 $L_3 = \{t_2, t_3, t_4\}$의 안전도는 $\infty$이다. $t_2$와 $t_4$를 반복해서 고르면 돈을 무한정 늘릴 수 있을 것 같지만, $1$번 물건이나 $2$번 물건을 구할 방법이 없어 그런 거래를 시도할 수 없기 때문이다.

물물교환 거래 리스트가 주어지면 그 리스트의 안전도를 측정하는 프로그램을 작성하시오.

첫째 줄에 물건의 개수 $N$과 물물교환 거래 리스트의 길이 $M$이 주어진다. ($1 \leq N \leq 1\,000, 1 \leq M \leq \min\left(N^2+N, 3\,000\right)$)

둘째 줄부터 $M$개의 줄에 걸쳐 거래 리스트 $L$의 정보가 다음 다섯 가지 형식 중 하나로 주어진다.

• $1\ c\ i$: $c$원을 들여 $i$번 물건을 살 수 있다.
• $2\ i\ c$: $i$번 물건을 팔아 $c$원을 벌 수 있다.
• $3\ i_1\ i_2$: $i_1$번 물건을 $i_2$번 물건과 교환할 수 있다.
• $4\ i_1\ c\ i_2$: $i_1$번 물건과 $c$원을 $i_2$번 물건으로 교환할 수 있다.
• $5\ i_1\ i_2\ c$: $i_1$번 물건을 $i_2$번 물건과 $c$원으로 교환할 수 있다.

$i$, $i_1$, $i_2$는 $1$ 이상 $N$ 이하의 정수이다. $c$는 $1$ 이상 $1\,000$ 이하의 정수이다. 각각의 수는 공백으로 구분되어 주어진다.

거래 리스트 $L$ 안의 $3$, $4$, $5$번 형식은 모두 $i_1 \neq i_2$를 만족한다.

$1$번 형식의 임의의 두 정보는 같은 $i$를 공유하지 않는다.

$2$번 형식의 임의의 두 정보는 같은 $i$를 공유하지 않는다.

$3$번, $4$번, $5$번 형식 중 하나로 들어온 임의의 두 정보는 같은 $i_1$과 $i_2$를 동시에 공유하지 않는다. 예를 들어 3 1 2와 4 1 1 2는 동시에 입력으로 주어지지 않는다. 그러나 3 1 2와 3 1 3은 동시에 입력으로 주어질 수 있는데, 이 둘은 $i_1$은 공유하지만 $i_2$는 공유하지 않기 때문이다.

모든 거래는 역방향을 보장하지 않는다. 예를 들어 입력 3 1 2는 $2$번 물건으로 $1$번 물건을 교환할 수 있다는 뜻이 아니다.

리스트의 안전도를 출력한다. 리스트의 안전도가 $\infty$라면 문자열 INF를 출력한다.