31913번 - 돈 복사 서브태스크

문제

GIST 하우스 중고장터에서는 돈을 특정 물건으로 바꿔주거나, 특정 물건을 다른 특정 물건으로 바꿔주는 이벤트를 진행하고 있다. 특정 물건을 특정 물건으로 바꿀 때는 추가적인 돈이 오갈 수 있다. GIST 하우스 중고장터는 무한히 많은 돈과 물건을 갖고 있기 때문에, 모든 거래는 재화가 존재하는 한 무한히 많이 할 수 있다. 단, 고객은 한 번에 물건을 최대 하나까지만 들고 있을 수 있다.

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 = \left\{t_1, t_2, t_3\right\}$에 든 거래만 허용한다고 가정하자. 그렇다면, $t_1, t_2, t_3$를 이 순서대로 선택하면 돈 20ドル$원을 돈 21ドル$원으로 늘릴 수 있다. 그리고 이를 무한히 반복하면 돈을 무한정 늘릴 수 있다. 이렇게 돈이 복사되면 대한민국 경제에 악영향을 끼칠 수 있기 때문에, 개발팀은 그런 상황을 막고 싶다. 따라서 개발팀은 거래들의 리스트가 주어지면 그 리스트가 안전한지 판별하고 싶다.

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

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

예를 들어, 리스트 $L_1 = \left\{t_1, t_2, t_3\right\}$의 안전도는 20ドル$이다. 20ドル$원의 돈을 갖고 가장 먼저 $t_1, t_2, t_3$를 선택하기를 반복하면 되기 때문이다. 그러나 19ドル$원의 돈을 갖고 있는 사람은 어떻게 하더라도 돈을 무한정 늘릴 수 없다. 또 리스트 $L_2 = \left\{t_3, t_4, t_5\right\}$의 안전도는 7ドル$이다.

한편 리스트 $L_3 = \left\{t_2, t_3, t_4\right\}$의 안전도는 $\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를 출력한다.

제한

서브태스크

힌트